shinobe179の日記

@shinobe179 の技術メモ・やらかし録

【Python】テキストファイルを開いて for で読み込むときは改行コードに注意しましょう(自戒

はじめに

あまりに初歩的過ぎて書くまでもないと思ったけど、そういうのだからこそ(自分のために)残しておく価値があると言い聞かせて書く。とは言え初歩的過ぎて凹んでいるので Twitter に流すのはやめておこうと思う。

結論

テキストファイルを for 文で 1 行ずつ読み込むときは改行コードがくっついてくるので必要に応じて処理する。

発端

CTF for Beginners 2020 の Spy に挑戦している最中、事前情報として提示された社員名簿 (employee.txt) を 1 行ずつ for 文で読み込んでログインを試行するスクリプトを組んだ。

import requests
import string
import json

URL = 'https://spy.quals.beginners.seccon.jp/'
with open('employees.txt') as f:
    for u in f:
        data = {
            'name': u,
            'password': ''
        }
        r = requests.post(URL, data=data)
        print(f'status: {r.status_code}, user: {u}, time: {r.text}') # 所要時間だけパースするのが面倒なので、 HTML ごとテキストに書き出して別途 grep した

見立てが正しければ、システムにアカウントが存在する場合とそうでない場合とで、ログイン処理にかかる時間に差が生じるはずだが、有意な差は得られなかった。しかし、手作業で 1 アカウントずつ確認していったら有意差が確認できた。結局、 flag は手作業頼りで取った。

原因

flag を取った後に data を print したら以下のようになっていた。 \n が含まれているせいで全アカウント存在しないものとして扱われたから、有意差が得られなかったということが分かった。

$ python3 enumerate.py
{'name': 'Arthur\n', 'password': ''}
{'name': 'Barbara\n', 'password': ''}
{'name': 'Christine\n', 'password': ''}
...

対策

rstrip()\n を除去すればよい。そもそも予想通りでない時点で print デバッグすればよかったし、 VSCode とか IDE を使っていればすぐに気づけた気がする。

import requests
import string
import json

URL = 'https://spy.quals.beginners.seccon.jp/'
with open('employees.txt') as f:
    for u in f:
        data = {
            'name': u.rstrip(),
            'password': ''
        }
        r = requests.post(URL, data=data)
        print(f'status: {r.status_code}, user: {u}, time: {r.text}') 

参考

qiita.com

【プログラミング】AtCoder ABC164-D の解法に関するメモ

はじめに

1 年以上ぶりの ABC は C 完でした。 D の理解にすごく苦労したので、メモを残します。

アプローチ

たくさんの解説記事を拝読しましたが、皆さん editorial と同じアプローチのようで、それを踏襲しました。大まかには以下のような感じです。

  • 1つ目の for 文で、 s の各区間の mod 2019 の結果の数を mods に保存する。
  • 2つ目の for 文で、 mods に格納された mod 2019 の結果が同一になる組み合わせの数を足し上げる。

atcoder.jp

s = input()[::-1]
v = 0
mods = [ 0 for i in range(2019) ]
mods[0] = 1
d = 1
 
for c in s:
    v += int(c) * d
    v %= 2019
    d *= 10
    d %= 2019
    mods[v] += 1
 
ans = 0
for n in mods:
    ans += (n * (n - 1)) // 2
 
print(ans)

なんで 10 と 2019 が互いに素だと、/ 10n を無視してよくなるの?

ここからは、私が個人的に理解できなかった部分の補足です。

この部分については、どの解説記事にも特に解説がなかったと思います。解説するまでもないことなのかもしれませんが、数学弱者が直感的にこの結果に辿り着くのは厳しかった……。

Twitterで明け方までうんうん唸っていたら、解説記事を投稿してくださっていたタムログさんが解説してくださいました。

※タムログさんの解説記事はこちら

タムログさんの例にのっかると、 2019 / 3 の mod 2019 を計算するときに、分母を無視すると 2019 ≡ 0 (mod 2019) ですが、分母を考慮に入れると 2019 / 3 = 693 ですから、 693 !≡ 0 (mod 2019)となって、結果が変わってしまう(分子だけだと合同だけど、分母込みだと合同でなくなる)わけです。これがなぜ起こるかというと、分母が 2019 と互いに素でない値だと、2019 の因数を除してしまうからですね。

以下は、分子を 20190 、分母を 10 もしくは 3 としたときの、それぞれの分母なし・ありでの合同式の真偽を確認したメモです。最後のほう、 6930 に見えますが 6730 です。

f:id:befs_anne:20200502200149j:plain

なんで mods[0] = 1 するの?

前述したような処理で解が求められるのは、「(区間A - 区間B) % 2019 ≡ 0 (mod 2019)」であるかどうかを、「区間A ≡ 区間B (mod 2019)」であることを検証することで求められるからです。各区間の mod 2019 の結果の中にはもちろん 0 も含まれるわけですが、区間 A が s[len(s-1)]、つまり s の右端の値を含む場合、区間 B は 0 ということになります。この場合の区間 B ついても区間のひとつとして扱い、0 ≡ 0 (mod 2019) としてカウントしなければ、仮に s の右端の値を含む区間 A の mod 2019 が 0 だった場合に、組み合わせの数が正しく計算されません。

なんで v %= 2019 するの? mod の結果は別で保存したほうがよくない?

n 回目のループで mod しようがしまいが、 n+1 回目のループでの v %= 2019 の結果には影響を及ぼしません(mod 2019 の結果に再度 mod 2019 しても値は変わらない)。計算効率の観点から見ると、v に mod した値を使うことで、後述の d %= 2019 の処理と同様効率を高めていることになると言えそうです。

なんで d %= 2019 するの?していいの?

これをしないと、ループ毎に d が 10 ずつ増えていくので、そのまま乗じてしまうと桁数がかなり大きくなってしまって v %= 2019 の処理に時間がかかってしまうんですね(実際、これがないと TLE になりました)。これをして結果に影響が及ばないかどうかについては、「(3 * 10000) % 2019」 の結果と 「(3 * 1924) % 2019」(※) の結果が、どちらも 1734 であることを以て証明できている気がします。

※…10000 % 2019 = 1924

さいごに

緑コーダー目指して、解けない問題に真剣に向き合ってみました。ふつうに延べ 1 日くらい費やしました。しんどかったです。数学やアルゴリズムの基礎理解が乏しいので厳しい戦いが続きそうですが、強くなるためにやっていこうと思います。

【プログラミング】複数キー、異順ソート(AtCoder ABC128-B)

はじめに

目から鱗だったのでメモします。異順ソートという言葉はないと思いますが便宜上名付けました。

問題

市名 点数 が複数個渡されるので、市名は昇順、かつ同じ市名なら点数は降順にして、番号(渡された順に1から採番)を出力する。

atcoder.jp

ポイント

各キーで昇順/降順が異なるソートをどのようにおこなうか?

私の実装

以下の記事を参考に、優先度が低いものから2回ソートした。

qiita.com

atcoder.jp

n = int(input())
rs = [ [i+1, input().split()] for i in range(n) ]

rs = sorted(rs, key=lambda a:int(a[1][1]), reverse=True)
rs = sorted(rs, key=lambda a:a[1][0])

for r in rs:
    print(r[0])

解説によると

https://img.atcoder.jp/abc128/editorial.pdf

問題文に合うようにレストランを並べるには、C++ でいう pair 型を利用すると簡単に実装できます。具 体的には、pair<pair<string,int>,int> の配列を用意し、レストランの情報を格納します。

ここまでは自力で辿り着いた。

first.second (2 番目のソート基準) に int 型で点数の −1 倍を入れ (点数が高い順に並べたいので)、

本来なら点数は降順でソートしなければならないが、-1倍することで市名と同じ昇順に揃えられるようにしてソートを1回で済ませてしまう、ということ。この発想はなかった。

試してみた

かなりシンプルな実装になった。sorted()のkeyを使ってキーを指定することをしないので、pair内の値の順番も重要になる。

atcoder.jp

n = int(input())
rs = []
 
for i in range(n):
    s,p = input().split()
    p = int(p)
    rs.append([[s, -p], i+1])
 
for r in sorted(rs):
    print(r[1])

柔軟な発想。。

『実践 bashによるサイバーセキュリティ対策』はセキュリティに興味があってbashに慣れていない人にすすめたい

はじめに

『実践 bashによるサイバーセキュリティ対策』を読みました。

公式: www.oreilly.co.jp

内容

第Ⅰ部では、bash正規表現の基礎的な使い方、セキュリティの CIA (機密性、完全性、可用性) + αとサイバーキルチェーンの考え方をさらっとやります。

第Ⅱ、Ⅲ、Ⅳ部では、第Ⅰ部で学んだ基礎を踏まえて、「セキュリティ関連のタスクをいかにして bash でこなすか」を、豊富なサンプルと共に示してくれています。

なんで bash …?

これについては 1 章で早々に触れていて、「技術的に見てもスクリプト言語として見てもクロスプラットフォームである」から、「セキュリティ業務における理想のテクノロジと位置付けている」としています。大体どんな Linux でも使える上に、最近じゃ Windows でも使えちゃいますからね。セキュリティの文脈に限らず、bash が便利な道具のひとつであることには、私も異論ありません。

紹介されているコマンドは LPIC レベル 1 相当のものがほとんど

だいたい以下のような顔ぶれです。もちろんこれが全てではないです。

Linux 触り始めた頃に欲しかった

正直、普段から業務で bash を駆使している方にとっては、読んでいて目から鱗が落ちることはそれほどなさそうです。

この本のいいところは、そういう中・上級者を満足させるようなニッチな情報ではなくて、基本的なコマンドに「このコマンドで、セキュリティ関係のこういうタスクをこなせます」という分かりやすい実例がついていることにあると思っています。grep を使ってログ検索とか、 curl を使って Web クローリングとか。練習に使えるサンプルコードも提供されています。

github.com

ゆえにこの本は初~中級者向けの本だと思っていて、漠然とセキュリティエンジニアに憧れていたものの Linux のこと全く分からなかった数年前の私にこの本があったら、テンションブチ上がってたこと間違いなしです。あの頃の私に必要だったのは、あずき色のお堅い参考書ではなく、ヘビがあしらわれたいかつい表紙のわりに、例が豊富で親切なこの本だったのです。

まとめ

我ながら「そんなやついねえだろ」というタイトルだったんですが、よくよく思い返してみれば自分がそうだったという話でした。もし同じような方がいらっしゃったらお手に取ってみてください。ボリュームもそれほどではないので、テンションブチ上げでこなしているうちに、あっという間に bash が苦じゃなくなるはずです。

【Python】リストや辞書を複製するときは copy() しなきゃいけないし、それらに値として更にリストや辞書が含まれているなら copy.deepcopy() しましょう(自戒

はじめに

はまったのでメモします。

リストや辞書を代入で複製しようとするとハマる

a_dict の構造をそのまま b_dict でも流用して、値だけ b に変えたれ~と思ったとき、代入によってそれをしようとすると、 a_dict['id'] まで b に変わってしまいます。調べるに、どうやらこれが参照渡しというやつらしい。基本情報で出てきた(落ちたけど

>>> a_dict = {'id': 'a'}
>>> a_dict
{'id': 'a'}
>>> b_dict = a_dict
>>> b_dict
{'id': 'a'}
>>> b_dict['id'] = 'b'
>>> b_dict
{'id': 'b'}
>>> a_dict
{'id': 'b'} # ここは a のままでいてほしい
>>>

解決策: copy() を使う

copy() を使うことで、参照渡しでなく値渡しをしましょう。

>>> a_dict = {'id': 'a'}
>>> a_dict
{'id': 'a'}
>>> b_dict = a_dict.copy()
>>> b_dict
{'id': 'a'}
>>> b_dict['id'] = 'b'
>>> b_dict
{'id': 'b'}
>>> a_dict
{'id': 'a'}
>>>

copy() で複製しようとしたリストや辞書の値に、リストや辞書が含まれているとハマる

今度は a_dict['pattern'] に配列を加えてから、 copy() で b_dict を作る。で、配列の内容を b っぽいものに変更すると、 a_dict['pattern'] も b っぽい内容に……なったはずなんだけど、ならない。 Python のバージョンが上がって(以下の REPL は 3.8.1) 、挙動が変わったのかな?

>>> a_dict = {'id': 'a', 'pattern': ['a', 'A']}
>>> a_dict
{'id': 'a', 'pattern': ['a', 'A']}
>>> b_dict = a_dict.copy()
>>> b_dict
{'id': 'a', 'pattern': ['a', 'A']}
>>> b_dict['id'] = 'b'
>>> b_dict['pattern'] = ['b', 'B']
>>> b_dict
{'id': 'b', 'pattern': ['b', 'B']}
>>> a_dict
{'id': 'a', 'pattern': ['a', 'A']} # a_dict['pattern'] も ['b', 'B'] になっちゃってた気がするんだが

……まあいいや、なったとして。それはガワの辞書は copy() によって値渡しできてるけど、中身のリストや辞書は参照渡しされているからみたいです。 Python のリファレンス中ではそれぞれ「浅いコピー」「深いコピー」と呼ばれていて、今回みたいにリストや辞書(クラスなども)が入れ子になっているオブジェクトを「複合オブジェクト」と呼ばれています。

docs.python.org

解決策: copy.deepcopy() を使う

import copy して、 b_dict = copy.deepcopy(a_dict) すると解消します。

...

コピーって、本当に奥が深いですネ!

shinobe179拝

【PowerShell】あのLinuxコマンドのPowerShell版が知りたいなら、とりあえずLinuxコマンドのまま実行しとけ(自戒)

はじめに

私用PCとしてしばらくUbuntuを使っていたんですが、ディスプレイとの接続など細かなところで問題が起きるので、Windowsに戻ってきました。Linux恋しさにWSLを常用しているんですが、WindowsとWSLとの行き来が完全に透過的とは言えずめんどくさいと思うことが多いし、会社支給PCなんかだとWSLが使えなかったりします。簡単なことはPowerShellを使ってWindows側で済ませちゃいたい、そんなモチベーションでこの記事を書くことにしました。え?Mac?高い。

Linuxコマンドのエイリアスがついているものがある

いくつかのPowerShellコマンドにはLinuxコマンドのエイリアスがあることを確認しています。helpコマンドに記載があるものとないものがあるようで、以下に列挙する例はそれらが混在しています。「Linuxの〇〇って、PowerShellではどういうコマンドなんだっけ?」と思ったら、とりあえず「help {{ 任意のLinuxコマンド }}」してみるか、いっそLinuxコマンドのまま実行してみるのも手ですね。

オプションが分からなければhelp(Get-Help)コマンドを使う

オプションはLinuxコマンドを踏襲していないので、覚えるまで「help {{ コマンド名 }}」で都度確認しましょう。ヘルプが出て来なければ「help {{ コマンド名 }} -Online」を実行すると各コマンドのヘルプページへジャンプします。

Get-Aliasでエイリアス一覧を確認する

ネット検索を駆使しながら対応表を作っていたところ、PowerShellコマンドのエイリアス一覧を表示する「Get-Alias」コマンドの存在を突き止めました。エイリアスがあるものはたいていこれで分かりそうですね。対応表なんていらなかったんや。

PS C:\Users\shinobe179> Get-Alias

CommandType     Name                                               Version    Source
-----------     ----                                               -------    ------
Alias           % -> ForEach-Object
Alias           ? -> Where-Object
Alias           ac -> Add-Content
Alias           asnp -> Add-PSSnapin
Alias           cat -> Get-Content
Alias           cd -> Set-Location
...

まとめ

総じて「{{ Linuxコマンド名 }} powershell」でググったらいいじゃん」という話なんですが、それをやる前にPowerShellの画面だけで解決できることもあるんやで、ということが分かりました。今後はInvoke-WebRequestなど個々のコマンドやピンポイントな課題に関する記事を上げていきたいと思います。

【AWS】AWS WAF と他リソースの紐づけ方が、紐づけ先リソースによって違うって話

はじめに

 オンプレだと値段も高くて運用もたいへんな WAF が、 AWS だとお手軽に入れられるってんで重宝されている AWS WAF。リージョナルリソース (ALB/API Gateway) と CloudFront に紐づけて使うことができます。

 WAF では、これら紐づけ先のリソースをリソースタイプとして区別しており、 WAF を扱う中で「どちらのタイプのリソースに紐づける WAF なのか」を意識しなければならない場面がたびたびあります。

 また、ただ単に区別がされているだけでなく、タイプによって紐づける方法が異なります。これを説明するのが今回の趣旨です。

基本原則

  • リージョナルリソースの場合は、 WAF(WebACL) 側から、紐づけるリソースを指定します。
  • CloudFront の場合は、 CloudFront(Distribution) 側から、紐づける WebACL を指定します。

マネジメントコンソールの場合

リージョナルリソース

 マネコンで WebACL を作るとき、「Associated AWS resources - optional」というセクションがあり、そこで指定できます(もちろん、作成した後も編集可能です)。

f:id:befs_anne:20200314142803p:plain

CloudFront

 CloudFront の Distribution 作成/編集画面で WebACL を指定できます。

※不思議なのは、 WebACL 作成画面でリソースタイプとして CloudFront distributions を選択していても、 Associated resources が選択できるという点。私が試したときはディストリビューションを指定しても実際には紐づけられませんでした。

CloudFormation の場合

※新しい API である AWS::WAFv2 リソースを前提とします。

 CloudFormation では、リソースタイプを AWS::WAFv2::WebACL 内で Type として指定します。リージョナルリソースの場合は REGIONAL 、CloudFront の場合は CLOUDFRONT です。

リージョナルリソース

AWS::WAFv2::WebACLAssociation というリソースを使って、紐づける リソースと WebACL の ARN をそれぞれ指定します。

https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-resource-wafv2-webaclassociation.html

Type: AWS::WAFv2::WebACLAssociation
Properties: 
  ResourceArn: String
  WebACLArn: String

CloudFront

 先ほどの WebACLAssociation のドキュメント中でも言及されていますが、CloudFrontでは AWS::CloudFront::Distribution を使って、 PropertiesDistributionConfig の中の、 WebACLId で、ディストリビューションに紐づける WebACL の ID を指定します。

実運用での話

 紐づけ先リソースによって、ベースとなるリソースが異なる(WAFv2 or CloudFront)こと、更に参照方法が異なる(ARN or WebACL ID)ことが、なんだか気持ち悪いし、実運用でも混乱しそうだなって感じです。

 例えば、 CloudFormation のベストプラクティスとして「ライフサイクルに応じてテンプレートを分ける」というのがありあます。このべスプラに則ると、「使用する WebACL」は WebACL を紐づける先のリソースと一緒に管理すべきだと解釈していて、これに則ると「ALB を管理するテンプレートの中にしれっと AWS::WAFv2::WebACLAssociation が混じってる」みたいなことになるわけです。気持ち悪くないですかこれ。 CloudFormation をゴリゴリ使う立場にはないんですが、CloudFormationist はこういう気持ち悪さを受け入れながら使っているんでしょうか?

おわりに

 なんか愚痴っぽくなってしまいましたが……やってる中で気になったことなのでメモしてみました。  AWS WAF 自体は、従来の WAF をクラウドらしいシンプルなものに定義し直した面白いプロダクトだと思っていて、今後のアップデートを期待したいです。特に、リージョナルリソースでも独自エラーページを返せたり、ステータスコードを変更できるようになると嬉しいです。