2019-04-20

LeetCode TwoSum をテストしながら解く

LeetCodeという競技プログラミングサービスがある。まだ始めたばかりなのだがとっつきやすい作りになっていて良い。そんなLeetCodeの問題 TwoSum を解いてみた。ただ解いてみたというのも面白くないので今回はテストコードも書きながら解答してみる。

TwoSum

問題はへのリンク https://leetcode.com/problems/two-sum/。問いは下記の通り。

数値の入った配列と整数値targetが与えられるので、配列の中から足すとtargetになる値の組み合わせを見つけ、その要素がどこにあるかを答えよ。必ず答えは存在するものとする。また別々の位置の値を必ず使用する事

以下に例を書く

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

テストコードを書く

コードを弄ってブラウザ上でテストしても問題はないが遅い。なので今回は手元ですぐに動作するテストコードを書いた。

package twosum

import (
    "reflect"
    "testing"
)

type testCase struct {
    array  []int
    target int
}

func TestTwoSum(t *testing.T) {
    tests := []struct {
        input  testCase
        output []int
    }{
        {testCase{[]int{2, 7, 11, 15}, 9}, []int{0, 1}},
        {testCase{[]int{2, 3, 4, 11, 15}, 6}, []int{0, 2}},
    }

    for i, tt := range tests {
        sum := twoSum(tt.input.array, tt.input.target)
        if !reflect.DeepEqual(sum, tt.output) {
            t.Errorf("tests[%d] failed - input: %+v - answer: %+v output: %d¥n", i, tt.input.array, tt.output, sum)
        }
    }
}

$GOPATH/src/leetcode/twosum/か何か適当なディレクトリでこれを書きgo test ./twosums/と入力すればお手軽テスト環境の完成。

あとはこのテストを通るような解答を考える。

解答

いくつか解法がある。 2つループを書いて総当たりする方法なんかは簡単だが、渡されるスライスが大きくなればなるほど時間計算量が増える。今回は一旦ハッシュテーブルを作成してその中から値の組み合わせを見つける解法で解いた。

package twosum

func twoSum(nums []int, target int) []int {
    var res []int
    res = make([]int, 2)

    numMap := make(map[int]int)
    for i, num := range nums {
        numMap[num] = i
    }

    for j, firstNum := range nums {
        comp := target - firstNum
        value, ok := numMap[comp]
        if !ok {
            continue
        }
        if value == j {
            continue
        }

        res[0] = j
        res[1] = value

        return res
    }

    return res
}

数値とその位置をハッシュテーブル化
targetからスライスから取り出した数値を引き、足してtargetになる数値を取り出す
ハッシュテーブルを確認し、足してtargetになる値があればその位置を返す
見つけるまで1-3を繰り返す

終わりに

Goのtest機能、楽に使えて良いですね。まだLeetCode始めたばかりなのでもっと問題を解いていこうと思います。

2019-01-16

RPISEC Malware Lab#01 をやったその2

RPISEC/Malwareとはマルウェア解析について体系的に学ぶことができる教材のこと。今回はその中のLab_01-2.malwareを解析した。

Lab_01-2.malware

1. これのMD5のハッシュ値は何？

02658bc9801f98dfdf167accf57f6a36

2. インポートされた関数やそれらのまとまりをいくつか取り上げてマルウェアでどのように使われているか説明せよ

ネットワーク関連(特にHTTP)のAPI - HTTPでファイルか何かをやりとりしている予想される
ファイルを読み書きするAPI - ファイルを読み込んだり書き換えたりしていると予想される
Sleep - 一定時間実行を遅らせることで解析を妨害していると予想される

3. ファイルの文字列で手がかりになりそうなものはどれか

cmd /c - コマンドを実行する
wuauclt.exe - 実行されるファイル名
69.25.50.10 - 接続先

4. このマルウェアを動かした時に予想される挙動はどのようなものか

ネットワーク越しにファイル(おそらくマルウェア)をダウンロードしサービスとして登録する

5. procmonでフィルタをかける際に使う名前とそれを使う理由

実行時のプロセス名。プロセスの挙動を追うため。

6. ホストベースのシグネチャとなりそうなものは何か(ファイルやレジストリキー、プロセスやらサービス、その他)。もしも存在していたらどのようなものか

wuauclt.exe use error! putf [transpeed] [filepath] 他にも文字列を見ているとコマンドを受け取り実行しそうな感じがする。 stringsで見ただけなのであくまで予想。

7. ネットワークベースのシグネチャとなりそうなものは何か(URL, 通信, その他)。もしも存在していたらどのようなものか

69.25.50.10

8. 解析を妨害する機能は存在するか。存在していた場合、どのようにそれを回避するか

sleep これを回避する方法 * sleep に飛ぶ命令をnopで潰す * 実行時にsleep命令を書き換えるを変更する * 実行時に時間計測系APIへの戻り値を書き換える

9. このマルウェアの目的は何か

ネットワークから他のマルウェアをダウンロードしサービスとして登録する

参考

Practical Malware Analysis

2019-01-15

RPISEC Malware Lab#01 をやった

RPISEC/Malwareとはマルウェア解析について体系的に学ぶことができる教材のこと。今回はその中のLab_01-1.malwareを解析した。

Lab_01-1.malware

1. このファイルはいつコンパイルされたか答えよ

コンパイル時間を確認するときはPEviewを利用する。 f:id:famasoon:20190115234151p:plain 画像のようにPEviewにファイルを読み込ませたあとIMAGE_NT_HEADERS->IMAGE_FILE_HEADER->TimeDataStampを確認する。ここにはコンパイルされた時間が格納されている。 2009/05/14 Thu 17:12:41 UTCがコンパイルされた時間だ。

2. インポートされた関数やそれらのまとまりをいくつか取り上げてマルウェアでどのように使われているか説明せよ

インポートされた関数を確認してみる。 CFF Explorer でLab01_01-1.malware を開く。次に画面左のImport Directory を選ぶ。下の画像のようにインポートに使われているdllが一覧表示される。 f:id:famasoon:20190115234244p:plain あとは気になるdllをクリックするだけで、そのdllからインポートされている関数を確認することができる。回答としては下のようになる。

SHELL32.dllからインポートされている"ShellExecuteExA" - プロセスを起動させる
ソケット関連のAPI - ネットワーク通信をする際に用いられる。
ファイル関連のAPI - ファイルを読みこんだり書き換えたりする。マルウェアをディスクに書き込むときに使われたりする。

3. ファイルの文字列で手がかりになりそうなものはどれか

PowerShell上でstringsコマンドを実行しファイル内の文字列を確認する。 f:id:famasoon:20190115234325p:plain (本当はfileinsightでstringsスクリプトを実行して文字列を抽出しようと思っていたが、なぜか動かなかった。あとで原因を調べる) 結果としては以下の文字列が気になった

http://www.ueopen.com/test.html - 通信先っぽい
60.248.52.95:443 - 同様に通信先っぽい
cmd.exe - コマンドを実行しそう

他には

*(SY)# cmd
*(SY)#
send = %d
*(SY)#
cmd.exe
exit
Open
 > nul
/c del

といった文字列が気になった。何かしら受け取ったコマンドを実行しそう。

4. このマルウェアを動かした時に予想される挙動はどのようなものか

問2の回答より、インポートされたAPIから察するにネットワーク通信をしファイルを書き込みマルウェアを実行させる。通信先は問3の回答で抽出した通信先と予想。

5. procmonでフィルタをかける際に使う名前とそれを使う理由

procmonとはプロセスのイベントを取得しログとして残してくれるツールのこと。ログを取得する際にフィルタを利用することで特定のイベント/プロセスについて情報を抽出できる。今回はプロセスの名前を使うと適切だと考えられる。理由としてはマルウェアの挙動を追うにはプロセス単位で見たほうが効率的だから。

6. ホストベースのシグネチャとなりそうなものは何か(ファイルやレジストリキー、プロセスやらサービス、その他)。もしも存在していたらどのようなものか

抽出した文字列から考えるに cmd.exe /c del でファイル削除をしそう。

7. ネットワークベースのシグネチャとなりそうなものは何か(URL, 通信, その他)。もしも存在していたらどのようなものか

抽出した文字列から下記のURLとIPアドレスがネットワークベースのシグネチャになりそう * http://www.ueopen.com/test.html * 60.248.52.95:443

8. 解析を妨害する機能は存在するか。存在していた場合、どのようにそれを回避するか

このファイルは自身を削除することで解析を妨害してくる。回避するには2つ手段が存在する。 1. ファイルをコピーして保存しておく 2. ファイルを削除する箇所の命令を無効化しておく

9. このマルウェアの目的は何か

抽出した文字列からネットワーク越しに何かしらのコマンドを実行する。いわゆるバックドアだと考えられる。

参考

Practical Malware Analysis

2019-01-06

minikube で OpenFaas を使う

kubernetes 環境で OpenFaas を使いたくなった。今回はローカルで試すためにも minikube を用いて OpenFaas をインストールする。

必要なもの

kubernetes kubernetesのドキュメントを参照してインストール。

sudo apt-get update && sudo apt-get install -y apt-transport-https
curl -s https://packages.cloud.google.com/apt/doc/apt-key.gpg | sudo apt-key add -
echo "deb https://apt.kubernetes.io/ kubernetes-xenial main" | sudo tee -a /etc/apt/sources.list.d/kubernetes.list
sudo apt-get update
sudo apt-get install -y kubectl

minikube ローカル環境でkubernetes を試せるツール。 minikube公式のドキュメントを参照してインストール。

curl -Lo minikube https://storage.googleapis.com/minikube/releases/latest/minikube-linux-amd64 \
&& chmod +x minikube
sudo cp minikube /usr/local/bin && rm minikube

インストールしたら下記コマンドで起動しておく

minikube start

faas-cli OpenFaasをCLIから操作するために使うツール。

curl -sSL https://cli.openfaas.com | sudo sh

helm k8sのパッケージ管理ツール。

curl https://raw.githubusercontent.com/kubernetes/helm/master/scripts/get | bash
kubectl -n kube-system create sa tiller \
 && kubectl create clusterrolebinding tiller \
      --clusterrole cluster-admin \
      --serviceaccount=kube-system:tiller

minikube 上にOpenFaas をインストール

公式のドキュメントを参考に構築する。まずはk8sの名前空間をyamlから作成する。

kubectl apply -f https://raw.githubusercontent.com/openfaas/faas-netes/master/namespaces.yml

次にhelmのチャートを追加する。

helm repo add openfaas https://openfaas.github.io/faas-netes/

今回はお試しでローカル環境に作るので認証機能を切って展開する。

helm repo update \
 && helm upgrade openfaas --install openfaas/openfaas \
    --namespace openfaas  \
    --set basic_auth=false \
    --set functionNamespace=openfaas-fn

minikube 上で展開されたか確認。

minikube service list

gateway-external にアクセスすればOpenFaasのダッシュボードを確認することができる。