2014年7月19日土曜日

SECCON 2014 オンライン予選 writeup - プログラミング300 あみだ

手動で2時間くらいかけて150問解いたところで挫折、 プログラムで解こうとコーディングを始めて1時間半で終了。 最初から組めや>自分

手順は以下の通り。

*が開始座標
*の[上下右左]が[||--]ならそれが進行方向、1つ進む
while 現在位置が[||--]
    現在位置の進行方向横が[-|]なら[|-]になるまで横にスライド
    1つ進行方向に進む
現在位置の文字出力


import java.io.*;
import java.util.*;

public class T {
 public static final int NO_DIRECTION = 0;
 public static final int TO_DOWN = 1;
 public static final int TO_UP = 2;
 public static final int TO_RIGHT = 3;
 public static final int TO_LEFT = 4;

 public static void main(String args[]) {
  InputStream is = null;
  OutputStream os = null;
  try {
   Process p = Runtime.getRuntime().exec("./amida");
   is = p.getInputStream();
   os = p.getOutputStream();
  } catch (Exception ex) {
   ex.printStackTrace();
  }
  try {
   new T().go(is, os);
  } catch (Exception ex) {
   ex.printStackTrace();
  }
 }

 public void go(InputStream is, OutputStream os) throws Exception {
  int no = 1;
  while (true) {
   int c;
   int width = 0;
   int height = 0;
   while ((c = is.read()) != '\n') {
    if (c == -1)
     System.exit(1);
    System.out.print((char)c);
   }
   System.out.println();

   StringBuffer sb = new StringBuffer();
   String line = null;
   ArrayList list = new ArrayList();
   while ((c = is.read()) != '?') {
    if (c == -1)
     System.exit(1);
    // System.out.println("2:" + c);
    if (c == '\n') {
     line = sb.toString();
     if (line.length() > 0) {
      width = line.length();
      list.add(line);
      sb = new StringBuffer();
     }
    } else {
     sb.append((char)c);
    }
   }

   is.read();

   height = list.size();
   char amida[][] = new char[height][width];
   int startX = 0;
   int startY = 0;

   for (int i = 0; i < list.size(); i++) {
    line = list.get(i);
    System.out.println(line);

    for (int j = 0; j < line.length(); j++) {
     amida[i][j] = line.charAt(j);
     if (amida[i][j] == '*') {
      startY = i;
      startX = j;
     }
    }
   }
   //System.out.println(startY + ":" + startX);

   int direction = NO_DIRECTION;
   int y = startY;
   int x = startX;
   if (startY == 0 && amida[1][startX] == '|') {
    direction = TO_DOWN;
    y++;
   } else if (startY == height - 1 &&
    amida[height - 2][startX] == '|') {
    direction = TO_UP;
    y--;
   } else if (startX == 0 && amida[startY][1] == '-') {
    direction = TO_RIGHT;
    x++;
   } else {
    direction = TO_LEFT;
    x--;
   }

   //System.out.println("direction:" + direction);
   //System.out.println(y + ":" + x);

   while (amida[y][x] == '|' || amida[y][x] == '-') {
    // System.out.println(y + ":" + x + ":" + amida[y][x]);
    if (direction == TO_DOWN || direction == TO_UP) {
     if (x > 0 && amida[y][x - 1] == '-') {
      x--;
      while (amida[y][x] != '|')
       x--;
      if (direction == TO_DOWN)
       y++;
      else
       y--;
     } else if (x < width - 1 && amida[y][x + 1] == '-') {
      x++;
      while (amida[y][x] != '|')
       x++;
      if (direction == TO_DOWN)
       y++;
      else
       y--;
     } else {
      if (direction == TO_DOWN)
       y++;
      else if (direction == TO_UP)
       y--;
     }
    } else if (direction == TO_RIGHT || direction == TO_LEFT) {
     if (y > 0 && amida[y - 1][x] == '|') {
      y--;
      while (amida[y][x] != '-')
       y--;
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     } else if (y < height - 1 && amida[y + 1][x] == '|') {
      y++;
      while (amida[y][x] != '-')
       y++;
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     } else {
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     }
    }
   }

   os.write(amida[y][x]);
   System.out.println("Ans=" + amida[y][x]);
   os.write('\n');
   os.flush();
   no++;
  }
 }
}

No.79だけバグってる模様。これだけハードコードで7。 (バグってたのは自分の頭、2014/07/22訂正) 1,000問解いてやっとキーが出てきた。

No.1000
            *  
| | |-| | | | |
|-| | |-| | |-|
| | | | | | | |
| |-| |-| | | |
|-| | | |-| |-|
| |-| | | | | |
|-| | |-| |-| |
| | |-| |-| |-|
| |-| |-| | | |
|-| | | | | |-|
| |-| |-| |-| |
| | |-| | | |-|
| | | | |-| | |
|-| |-| | |-| |
| |-| | | | | |
| | |-| | |-| |
|-| | | |-| | |
| | | |-| |-| |
| | |-| |-| |-|
1 2 3 4 5 6 7 8
Ans=3
FLAG{c4693af1761200417d5645bd084e28f0f2b426bf}

2014年5月1日木曜日

CentOS 6.5 カーネル再構築 2.6.32-431.11.2.el6.x86_64編

CentOSのカーネル再構築メモ。
最新のLinuxカーネルで構築し直すんじゃなくて、今動いているシステムのカーネルソースいじって遊ぶぜ的な人向けの手順です。

バージョンによって前提パッケージが違ったり、ソースをダウンロードしてくるところが違ったり面倒だったので、なるべく汎用性ありそうな書き方で。

まずOS自体を最新バージョンにアップデート。

# yum update
# reboot

私がやったとき(2014/04/29)の最新バージョンは2.6.32-431.11.2です。64ビット版です。

続いて開発環境をインストール。これは他サイトからの受け売り。

# yum groupinstall "Development tools"  


で、次にその他の前提パッケージのインストール、ってのがありがちな書き方ですが、その前にソースをダウンロードして、インストールを試みます。ソースの置き場所もその時々で違ったりするので、CentOSのサイトで確認するといいんじゃないかと思います。
2014/04/29時点では、トップ→Get CentOS Linux Now→Need the Source?
とたどって、ソース置き場からとってきました。これを一般ユーザでインストールします。

$ wget http://vault.centos.org/6.5/updates/Source/SPackages/kernel-2.6.32-431.11.2.el6.src.rpm
$ rpm -ivh kernel-2.6.32-431.11.2.el6.src.rpm


で、rpmbuildを動かすと必要な前提パッケージを教えてくれます。 これがバージョンによって違ったりするようなので、違うバージョンの手順を真似るよりはrpmbuildに聞いた方が確実なんじゃないかと。

$ cd ~/rpmbuild/SPECS
$ rpmbuild -bp kernel.spec --target=x86_64
ビルド対象プラットフォーム: x86_64
ターゲット x86_64 用にビルド中
エラー: ビルド依存性の失敗:
        xmlto は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        asciidoc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        elfutils-libelf-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        elfutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        zlib-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        binutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        newt-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        python-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        audit-libs-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        perl(ExtUtils::Embed) は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        hmaccalc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています


で、これらをインストールします。perl(ExtUtils::Embed)はさすがにクォーテーションで囲まないとエラーになると思います。

# yum install xmlto asciidoc elfutils-libelf-devel elfutils-devel zlib-devel binutils-devel newt-devel python-devel audit-libs-devel "perl(ExtUtils::Embed)" hmaccalc


この後もう一回rpmbuild実行、~/rpmbuild/BUILDの該当バージョンというか、できてるディレクトリの下に行ってmake、インストールします。

$ rpmbuild -bp kernel.spec --target=x86_64
$ cd ~/rpmbuild/BUILD/kernel-2.6.32-431.11.2.el6/linux-2.6.32-431.11.2.el6.x86_64
$ vi Makefile
EXTRAVERSION = -selinux
$ make
# make modules_install
# make install
# reboot

ここではMakefileのEXTRAVERSIONを-selinuxにしています(個人的にSELinuxまわりの研究でやっているので)。
この場合OS起動時eをタイプすることで表示されるブートオプションの画面で、構築したカーネルが2.6.32-selinuxと表示されます。

2014年2月27日木曜日

Ubuntu 13.10 x64 + Hadoop 1.2.1 + Mahout 0.9

Mahout 0.9 のインストールでいろいろ引っかかったのでメモ。

Ubuntu13.10 x64にmahoutユーザでインストール。

ひっかかってた最大の理由はMahout0.9が前提にしているHadoopのバージョンが1.2.1ってことに気づくのが遅かったからでした(Mahout0.9のパッケージの中にlib/hadoop/hadoop-core-1.2.1.jarってのがあった)。

  • sshd準備

# apt-get install openssh-server
$ ssh-keygen -t rsa -P ""
$ cat .ssh/id_rsa.pub >> .ssh/authorized_keys
$ chmod 600 .ssh/authorized_keys


  • IPv6停止(他サイトの受け売り)

# vi /etc/sysctl.conf
(追加)
net.ipv6.conf.all.disable_ipv6 = 1
net.ipv6.conf.default.disable_ipv6 = 1
net.ipv6.conf.lo.disable_ipv6 = 1
# reboot


  • JDKインストール

$ tar zxvf jdk-7u51-linux-x64.tar.gz
# mv jdk1.7.0_51 /usr/local
# ln -s /usr/local/jdk1.7.0_51 /usr/local/jdk


  • Hadoopインストール

$ tar zxvf hadoop-1.2.1.tar.gz
# mv hadoop-1.2.1 /usr/local
# ln -s /usr/local/hadoop-1.2.1 /usr/local/hadoop

$ vi /usr/local/hadoop/conf/hadoop-env.sh
(追加)
export JAVA_HOME=/usr/local/jdk

$ vi /usr/local/hadoop/conf/core-site.xml
(追加)
  <property>
    <name>fs.default.name</name>
    <value>hdfs://localhost:9000</value>
  </property>

$ vi /usr/local/hadoop/conf/hdfs-site.xml
(追加)
  <property>
    <name>dfs.replication</name>
    <value>1</value>
  </property>
  <property>
    <name>dfs.name.dir</name>
    <value>/home/hadoop/dfs/name</value>
  </property>
  <property>
    <name>dfs.data.dir</name>
    <value>/home/hadoop/dfs/data</value>
  </property>

$ vi /usr/local/hadoop/conf/mapred-site.xml
(追加)
  <property>
    <name>mapred.job.tracker</name>
    <value>localhost:9001</value>
  </property>
  <property>
    <name>mapred.local.dir</name>
    <value>/home/hadoop/mapred</value>
  </property>

hdfs-site.xmlのdfs.name.dir、dfs.data.dirあたりは書いておかないと/tmpの下に作られるため、システムリブートの度に消されてあとでイラっときます。

  • Mahoutインストール

$ tar zxvf mahout-distribution-0.9.tar.gz
# mv mahout-distribution-0.9 /usr/local
# ln -s /usr/local/mahout-distribution-0.9 /usr/local/mahout


  • 環境設定

(追加)
JAVA_HOME=/usr/local/jdk
HADOOP_HOME=/usr/local/hadoop
MAHOUT_HOME=/usr/local/mahout
PATH=${JAVA_HOME}/bin:${HADOOP_HOME}/bin:${MAHOUT_HOME}/bin:/usr/lib/lightdm/lightdm:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games
export JAVA_HOME MAHOUT_HOME PATH
$ exit


  • ネームノードフォーマット

$ hadoop namenode -format


  • Hadoop起動

$ start-all.sh
$ jps
4917 JobTracker
4539 NameNode
5105 Jps
4680 DataNode
4832 SecondaryNameNode
5060 TaskTracker

6つ起動しない場合は/usr/local/hadoop/logsの下の*.logを参照。ちょっとしたことで動かなくなったりします。

で、ここでMahoutのサンプル起動しますがエラーになります。

$ cd /usr/local/mahout/examples/bin
$ ./classify-20newsgroups.sh
Please select a number to choose the corresponding task to run
1. cnaivebayes
2. naivebayes
3. sgd
4. clean -- cleans up the work area in /tmp/mahout-work-mahout
Enter your choice : 2
    :
    :
Exception in thread "main" java.io.FileNotFoundException: File does not exist: /tmp/mahout-work-mahout/20news-all


いろいろ調べた結果、このサンプルはデータをネットワークからダウンロードしますが、環境変数HADOOP_HOMEが設定されていないとhdfs上にコピーしてくれません。
HADOOPはHADOOP_HOME設定してると「Warning: $HADOOP_HOME is deprecated.」って文句行ってくるのにMahoutのサンプルはそれを前提にしているってオチでした。


$ export HADOOP_HOME=/usr/local/hadoop


すると今度は動きます。


=======================================================
Statistics
-------------------------------------------------------
Kappa                                       0.8753
Accuracy                                   90.3805%
Reliability                                85.7215%
Reliability (standard deviation)            0.2163

14/02/27 13:45:07 INFO driver.MahoutDriver: Program took 18474 ms (Minutes: 0.3079)


まだ不完全なんだなという印象。

2014年2月18日火曜日

SECCON 2013 CTF オンライン予選 数毒 writeup

そもそも修論の追い込みで忙しい時期なので今回参加しないつもりでしたが、蓋を開ければ「解かないとあとで何言われるかわからない」数独があったのでしょうがない、この1問だけやりました。

DEFCON CTF 2013のゲリラプログラミングのスライドパズル同様、過去に自分で作って晒したコードをダウンロードして流用パターンです。

出題サーバにtelnetでアクセスするとこんな問題が表示されます。


'suDOKU(su-poison)' challenge for SECCON 2013.
by KeigoYAMAZAKI, 2013.11.22-


* Stage 1

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |8|.|.|.|.|.|.|.|.|
B |.|.|3|6|.|.|.|.|.|
C |.|7|.|.|9|.|X|.|.|
  $-+-+-$-+-+-$-+-+-$
D |.|5|.|.|.|7|.|.|.|
E |.|.|.|.|4|5|7|.|.|
F |.|.|.|1|.|.|.|3|.|
  $-+-+-$-+-+-$-+-+-$
G |.|.|1|.|.|.|.|6|8|
H |.|.|8|5|.|.|.|1|.|
I |.|9|.|.|.|.|4|.|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 2, how many solutions does this sudoku have?  => answer: 

注:証拠のデータ残していなかったので、問題は別のやつ貼り付けてます。

数独の問題なんですが中にXってのがあって、Xが2の時解はいくつあるか?って聞いてきます。 1盤面あたり複数この質問が来て、クリアすると次の盤面っていう繰り返しです。

以前、自分で作ったPrologのコードはこんなカンジです。
https://github.com/minetosh/sudoku/tree/master/prolog


sudoku(Rows) :-
    maplist(seigen, Rows), cols(Rows), blks(Rows),
    maplist(fd_labeling, Rows).

cols([[]|L]).
cols(L) :-
    maplist(nth(1), L, X), seigen(X), maplist(delete, L, X, NL), cols(NL).

blks([]).
blks([X, Y, Z|L]) :- blks2(X, Y, Z), blks(L).

blks2([],_,_).
blks2([X1, X2, X3|XL], [Y1, Y2, Y3|YL], [Z1, Z2, Z3|ZL]) :-
    seigen([X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3]), blks2(XL, YL, ZL).

seigen(X) :- fd_domain(X, 1, 9), fd_all_different(X).


gprolog --consult-file sudoku.pl で起動した後、問題入力はこうやります。


Row1 = [8, _, _, _, _, _, _, _, _],
Row2 = [_, _, 3, 6, _, _, _, _, _],
Row3 = [_, 7, _, _, 9, _, 2, _, _],
Row4 = [_, 5, _, _, _, 7, _, _, _],
Row5 = [_, _, _, _, 4, 5, 7, _, _],
Row6 = [_, _, _, 1, _, _, _, 3, _],
Row7 = [_, _, 1, _, _, _, _, 6, 8],
Row8 = [_, _, 8, 5, _, _, _, 1, _],
Row9 = [_, 9, _, _, _, _, 4, _, _],
sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).


解は次のように表示されます。


Row1 = [8,1,2,7,5,3,6,4,9]
Row2 = [9,4,3,6,8,2,1,7,5]
Row3 = [6,7,5,4,9,1,2,8,3]
Row4 = [1,5,4,2,3,7,8,9,6]
Row5 = [3,6,9,8,4,5,7,2,1]
Row6 = [2,8,7,1,6,9,5,3,4]
Row7 = [5,2,1,9,7,4,3,6,8]
Row8 = [4,3,8,5,2,6,9,1,7]
Row9 = [7,9,6,3,1,8,4,5,2] ?


検索してこのプログラムにたどり着いても複数解表示させる方法がわからなければ意味ないんですが、Prologで次の解を表示させるには、解を表示した後の?プロンプトに対して;(セミコロン)を入力します。解がある間これを繰り返します。
1問あたり制限時間は3分なので、この間に全解を手動で表示できる程度であれば、問題をこのプログラムの入力形式に変換してコピペ、セミコロンを入力し続けて解の数を数えればおkとなります。

解の数が2桁程度までなら上記方法でも十分間に合いますが3桁以上になったらきついと思うので、その時はjavaでI/O制御するプログラム作るつもりでいました。

とりあえず問題変換&コピペの手法を試すのに、以下のプログラムを作りました。


import java.io.*;

public class P200 {
 public static void main(String args[]) {
  try {
   InputStreamReader isr = null;
   try {
    isr = new InputStreamReader(System.in, "UTF-8");
    BufferedReader br = null;
    try {
     br = new BufferedReader(isr);
     String line = null;
     char c;
     while (true) {
      line = br.readLine();
      if (line.charAt(0) != ' ') {
       System.out.print("Row");
       System.out.print(line.charAt(0) - 'A' + 1);
       System.out.print("=[");
    System.out.print(a(line.charAt(3))); System.out.print(",");
    System.out.print(a(line.charAt(5))); System.out.print(",");
    System.out.print(a(line.charAt(7))); System.out.print(",");
    System.out.print(a(line.charAt(9))); System.out.print(",");
    System.out.print(a(line.charAt(11))); System.out.print(",");
    System.out.print(a(line.charAt(13))); System.out.print(",");
    System.out.print(a(line.charAt(15))); System.out.print(",");
    System.out.print(a(line.charAt(17))); System.out.print(",");
    System.out.print(a(line.charAt(19))); System.out.println("],");
       if (line.charAt(0) == 'I') {
        System.out.println(
 "sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9])."
        );
       }
      }
     }
    } finally {
     if (br != null) br.close();
    }
   } finally {
    if (isr != null) isr.close();
   }
  } catch (Exception ex) {
   ex.printStackTrace();
  }
 }

 public static char a(char c) {
  if (c == '.')
   return '_';
  else
   return c;
 }
}


このプログラムで、


   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |8|.|.|.|.|.|.|.|.|
B |.|.|3|6|.|.|.|.|.|
C |.|7|.|.|9|.|X|.|.|
  $-+-+-$-+-+-$-+-+-$
D |.|5|.|.|.|7|.|.|.|
E |.|.|.|.|4|5|7|.|.|
F |.|.|.|1|.|.|.|3|.|
  $-+-+-$-+-+-$-+-+-$
G |.|.|1|.|.|.|.|6|8|
H |.|.|8|5|.|.|.|1|.|
I |.|9|.|.|.|.|4|.|.|
  $-+-+-$-+-+-$-+-+-$


が、


Row1 = [8, _, _, _, _, _, _, _, _],
Row2 = [_, _, 3, 6, _, _, _, _, _],
Row3 = [_, 7, _, _, 9, _, X, _, _],
Row4 = [_, 5, _, _, _, 7, _, _, _],
Row5 = [_, _, _, _, 4, 5, 7, _, _],
Row6 = [_, _, _, 1, _, _, _, 3, _],
Row7 = [_, _, 1, _, _, _, _, 6, 8],
Row8 = [_, _, 8, 5, _, _, _, 1, _],
Row9 = [_, 9, _, _, _, _, 4, _, _],
sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).


になるので、X手前までPrologへコピペ、Xのところに示された数字入力、Xより後ろコピペ、セミコロン入力しながら数えて、の繰り返しでクリア出来ました。

結局私がやったときは解の数は0,1,2しかなく結構あっさり終わってしまいました。他の方のWriteupを見ると19っていうのもあったようです。

スコア画面に「あなたが一番最初にこの問題をときました」みたいに表示されていたので、多分そうゆうことなんだと思います。