LACのインターンシップに参加しました

はじめに

2018/8/10に開催されたLACのインターンシップに参加してきました!

参加したコースは,JSOCオペレーション実践コース「ログ解析体験」です.
以前からJSOCでの業務には興味があったので応募し参加しました.

会場到着まで

出発地の大塚から会場の永田町まで東京メトロ南北線を利用したのですが,通勤ラッシュと重なって地獄を見ました.
出発前に空いてる路線を確認したほうがいいですね...orz

内容

内容はコースタイトル通り「ログ解析」を行いました.

Webサーバの通信内容を解析して,どのような脆弱性(e.g. SQLi, XSS, Directory Traversal, OS Command Injection, etc.)を突いた攻撃が行われようとしているのか,また,マルウェアのC&Cサーバとの通信内容を解析して,マルウェアがどのようなデータやコマンドを通信しているのかといったことを,パケットキャプチャファイルとWiresharkを用いて解析しました.

CTFで問題を解くときにWiresharkを用いたりpcapファイルを解析したり...といった経験はありましたが,「どの通信が怪しいのか」「なぜその通信が怪しいのか」「攻撃者はどのような脆弱性を狙っているのか」「攻撃の結果どうなったのか」といったことを細かくトレースし,レポートにまとめるといった経験は初めてだったので,とても良い勉強になりました.

加えて,既存のログの解析だけではなく,NIDSの1つであるSnortを用いて攻撃パケットのDetectionを行うといった作業も行いました.

Snortのルール記述文法を学んだ後,マルウェアによって自動的に発生する通信や既知の脆弱性を狙った通信(MS15-034怖い!)を,実際に作成したルールで検知できるようにしました.

うまくルールを作成したと思っても,なんらかの抜け道があったり,他の正常なパケットを不正とみなして検知してしまう(FP)といった問題が発生することが多々あり,ルール作成の困難さを体感することができました.

おわりに

インターンシップを通して,ネットワークセキュリティ関連のツールの扱い方や,実際に業務で行われているログ解析の手順といったことを,実際に手を動かしながら身につけることができたと感じています.

JSOCの見学も行わせていただいたのですが,遠目で見ただけでも大量のパケットやログがそこかしこと流れていっているのが見え,10000件程度のパケットの解析でゼエゼエ言っていた身からすると...という感じでした.はやくプロになりたいです...💪

今回のインターンシップといった機会を与えてくださったLACの関係者の方々,ありがとうございました!

AtCoder Beginner Contest 105 に参加しました(Python)

サイトへのURL

AtCoder Beginner Contest 105 - AtCoder

以下では,li_input()関数を用います.

def li_input():
    return [int(_) for _ in input().split()]

A問題

問題文

高橋君は N 枚の AtCoder せんべいを K 人の AtCoder 参加者になるべく公平に配ることにしました。 N 枚すべてのせんべいを配るとき、せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)の最小値を求めてください。  

解法

せんべいN枚をK人に均等に分けられる時,答えは0です.
均等に分けられない時,答えは1です.

ソースコード

def main():
    N, K = li_input()

    if N % K == 0:
        print(0)
    else:
        print(1)


main()

B問題

問題文

ABC 洋菓子店では, 1 個 4 ドルのケーキと 1 個 7 ドルのドーナツが売られている. このとき, 合計金額が N ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

解法

ケーキを買う個数をx,ドーナツを買う個数をyとします.
また,合計金額pp = 4x + 7yとします.

問題文の条件より,Nはたかだか100なので,
1 <= p <= 100となるようなxyを全探索によって求めれば良いです.

ソースコード

def main():
    l = []

    for i in range(100):
        for j in range(100):
            if i * 4 + j * 7 <= 100:
                l.append(i * 4 + j * 7)

    N = int(input())

    if N in l:
        print("Yes")
    else:
        print("No")

C問題

問題文

f:id:Szarny:20180812013256p:plain

解法

公式解法とは全く異なります

細かいところについては,ソース内に書いているので省きます.
通常の10進数>2進数変換の際と同じように考えました.

  1. 最上位ビットの位置を決める(上位から順に b_k b_{k-1} b_{k-2} ... b_1 b_0 とする 当然b_{k}1)
  2. 2.1. 各ビットの-2進数の位を c_k c_{k-1} c_{k-2} ... c_1 c_0 とする
    2.2. 現在の値を c_kの値とする
    2.3. i = k-1とする

  3.  c_{i}が正の数である場合は4へ 負の数である場合は5へ
  4. 4.1.  c_{j} (j < i) である全ての正の数の総和と現在までの値を足してNに届かなければ, b_{i}のビットを立てる
    4.2. 現在の値 = 現在の値 +  c_{i}とする.

  5. 5.1.  c_{j} (j < i) である全ての負の数の総和と現在までの値を足してNを上回れば, b_{i}のビットを立てる
    5.2. 現在の値 = 現在の値 +  c_{i}とする.

  6. iをデクリメントして3に戻る

のような感じです.

ソースコード

c = []


# (i < limit, c[i] > 0となるc[i]の数を足して行った結果) + 現在の値 が
# Nを下回ればc[limit]を足す必要がある
def is_lower(limit, c_value, N):
    add_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# (i < limit c[i] < 0となるc[idx]の数の総和) + 現在の値 が
# Nを上回ればc[limit]を引く必要がある
def is_over(limit, c_value, N):
    sub_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    global c

    N = int(input())
    c_value = None

    # コーナーケース
    if N == 0:
        print(0)
        return

    # 位を事前に計算
    for i in range(50):
        c.append((-2)**i)

    # NがPositiveの場合
    # (-2)**i (i=2k) の総和が目的の値を超えるところが最上位ビット
    if N > 0:
        tmpsum = 0
        for i in range(50):

            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

    # NがNegativeの場合
    # (-2)**i (i=2k+1) の総和が目的の値を下回るところが最上位ビット
    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

    ans = "1"

    for c_idx in range(idx - 1, -1, -1):
        # c[c_idx]がNegativeのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']<0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを上回ってしまうなら,c[c_idx]を加算する必要がある
        if c[c_idx] < 0:
            if is_over(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

        # c[c_idx]がPositiveのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']>0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを下回ってしまうなら,c[c_idx]を加算する必要がある
        else:
            if is_lower(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

    print(ans)


main()

D問題

問題文

f:id:Szarny:20180812020237p:plain

解法

累積和を用います.
ただし,ここでは各累積和の Mの剰余が知れればいいので,計算時に Mの剰余のみを格納します.
つまり, A_{1}から A_{k}までの総和を Mで割った値を C_{k}とします.
(ただし, C_{0} = 0とする.)

ここで,条件を満たすような (l, r)の総数というのは, C_{l-1} = C_{r}となるような (l, r)において,それぞれの (l, r)の2つの組み合わせの個数の和のことです.
なぜなら, C_{l-1} = C_{r} ( C_{l-1} - C_{r} = 0)のとき, A_{l} A_{l+1} ... A_{r-1} A_{r}の総和は Mの倍数になるからです.
これを数え上げれば解くことができます.

ソースコード

import collections

def main():
    N, M = li_input()
    A = li_input()

    ans = 0
    d = collections.defaultdict(lambda: 0)

    cumsum = [0]
    c_sum = 0
    for a in A:
        c_sum = (c_sum + a) % M
        cumsum.append(c_sum)

    for c in cumsum:
        d[c] += 1

    for v in d.values():
        if v >= 2:
            ans += v * (v - 1) // 2

    print(ans)


main()

AtCoder Beginners Selection をPythonで解く

はじめに

競技プログラミングをぼちぼちやっています.
復習も兼ねて,Tasks - AtCoder Beginners SelectionPython(3)で解いていきます.

はじめてのあっとこーだー(Welcome to AtCoder

問題文の通りにやるだけです.

def main():
    a = int(input())
    b, c = [int(_) for _ in input().split()]
    s = input()

    print(a + b + c, s)

main()

Product

こちらも問題文の通りにやるだけです. 三項演算子を使っています.

def main():
    a, b = [int(_) for _ in input().split()]
    print("Even") if a * b % 2 == 0 else print("Odd")

main()

Placing Marbles

1の数を数えます.
count関数で特定の文字を文字数を数えることができるのでそれを利用します.

def main():
    print(input().count("1"))

main()

Shift only

全要素を割れなくなるまで2で割り,割れなくなった時のループ回数を表示しています.

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()

Coins

単純な全探索です.
O(n^3)ですが,A, B, Cはたかだか50なので大丈夫.

import sys

def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())

    ans = 0

    for nA in range(A + 1):
        for nB in range(B + 1):
            for nC in range(C + 1):
                if nA * 500 + nB * 100 + nC * 50 == X:
                    ans += 1

    print(ans)

main()

Some Sums

str(num)で文字列化し,list(...)によって各文字を要素とする配列に変換し,map(...)によって再度整数型にした後,sum(...)で合計を計算しています.

def main():
    N, A, B = [int(_) for _ in input().split()]

    ans = 0

    for num in range(1, N + 1):
        if A <= sum(map(int, list(str(num)))) <= B:
            ans += num

    print(ans)

main()

Card Game for Two

両者が最適な戦略をとる(=場にある数のうち最大のものを取り続ける)ので,
数を降順に並べ替えた後,
 1, 3, 5, ...番目に大きい数を加算し, 2, 4, 6, ...番目に大きい数を減算すれば良いです.

def main():
    N = int(input())
    A = sorted([int(_) for _ in input().split()], reverse=True)

    ans = 0
    for i, a in enumerate(A):
        if i % 2 == 0:
            ans += a
        else:
            ans -= a

    print(ans)

main()

Kagami Mochi

一見ややこしそうですが,入力値の重複を除くだけで解くことができます.
色々方法はありそうですが,ここでは単純にset関数を用いて集合化することで要素をユニークにしています.

def main():
    N = int(input())
    D = []

    for _ in range(N):
        D.append(int(input()))

    print(len(set(D)))

main()

Otoshidama

全探索しようとするとO(n^3)アルゴリズムになりそうですが,
10000円札の枚数と5000円札の枚数を決定した時点で

1000円札の枚数 = 全体の枚数 - 10000円札の枚数 - 5000円札の枚数

となり1000円札の枚数を決定できるため,計算量をO(n^2)に削減することが可能です.

import sys

def main():
    N, Y = [int(_) for _ in input().split()]

    for n_10k in range(N+1):
        for n_5k in range(N - n_10k + 1):
            n_1k = N - n_10k - n_5k

            if n_10k * 10000 + n_5k * 5000 + n_1k * 1000 == Y:
                print(n_10k, n_5k, n_1k)
                sys.exit()

    print(-1,-1,-1)

main()

白昼夢 / Daydream

 Tに文字列を付け足して Sを作ろうとするのではなく,
 Sから文字列を削除することで T(=空文字列)を作ることができるかを調べます.

ここで,前方から検索すると,dreamerereraseerが混じって面倒です.
後方から検索を行うことで,erに関係なく Sから文字列を削除することが可能です.

def main():
    S = input()

    while len(S) >= 5:
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

main()

Traveling

AtCoDeerくんが時刻  t に座標  (x, y) にいるとします.
そして,時刻  t' に座標  (x', y') に移動しなければいけない状況を考えます.

ここで, distance = |(x' - x)| + |(y' - y)|とします.
また, timedelta = t' - t とします.

 distance > timedelta であるとき,つまり移動量が移動可能時間よりも大きいとき,時間内に移動を終えることは不可能です.
よって,Noを出力して終われば良いです.

 distance = timedelta であるとき,つまり移動量と移動可能時間が同じとき,時間内に移動を終えることが可能です.
よって,Yesを出力し次の条件に移ります.

 distance \lt timedelta であるとき,つまり移動量より移動可能時間が大きいときは,条件を達成できる場合とできない場合があります.

例えば,時刻  0 に座標  (0, 0) にいて,時刻  4 に座標  (2, 0) に移動しなければならない時は (0, 0), (1, 0),  (2, 0),  (1, 0),  (2, 0)のように,目的の座標にたどり着いた後行ったり来たりを繰り返せば条件を達成することができます.

一方で,時刻  0 に座標  (0, 0) にいて,時刻  5 に座標  (2, 0) に移動しなければならない時は (0, 0),  (1, 0),  (2, 0),  (1, 0),  (2, 0),  ...となり,どう歩いても目的の座標に目的の時刻にたどり着くことは不可能です.

まとめると, distance \lt timedelta であるときは,ゴールにたどり着いた後,行ったり来たりして残り時間を消費できれば条件を達成することができるといえます.

これは, timedelta - distance の値,つまり目的地にたどり着いた後の余裕時間が  2 で割り切れるかを調べるとわかります.
なぜなら,目的地にたどり着いた後の余裕時間の値が  2 で割り切れるとき,行ったり来たりして目的の座標に戻ることができるからです.

import sys

def main():
    N = int(input())
    t, x, y = 0, 0, 0

    for _ in range(N):
        next_t, next_x, next_y = [int(__) for __ in input().split()]

        delta_t = next_t - t
        distance = abs(next_x - x) + abs(next_y - y)

        if distance > delta_t:
            print("No")
            sys.exit()

        if (delta_t - distance) % 2 != 0:
            print("No")
            sys.exit()

        t, x, y = next_t, next_x, next_y

    print("Yes")

main()

おわりに

はやく水色になりたい