2017-01-14

アナグラム判定メソッドの実行速度を比較してみた

今回は前回の続きといいますか、似たような問題に対する実装を複数パターンあったのでその速度を比較してみました。

問題

二つの文字列が与えられた時、片方がもう片方の並び替えになっているかどうかを決定するメソッドを書いてください。

前提条件：空白や大文字小文字も区別する。文字コードはASCIIコードだけで構わない。

というわけで書いてみました。

実装コード

static boolean MyisAnagram(String word1,String word2){
        int sumCode_1=0;
        int sumCode_2=0;
        
        if(word1.length()!=word2.length())
            return false;
        
        for(int i=0;i<word1.length();i++){
            sumCode_1 += word1.charAt(i);
        }
        for(int i=0;i<word2.length();i++){
            sumCode_2 += word2.charAt(i);
        }
        
        if(sumCode_1 == sumCode_2){
            return true;
        }
        else{
            return false;
        }
        
    }

あ、今回はjavaです。Eclipseで書いているので書いてる途中に間違えがすぐわかるので便利です。

上記のコードは自分が完全に０から考えたメソッドです。

文字列の文字コードを全て足し合わせて一致しているならアナグラムであると言えます。

中々スマートに書けたかなとは思います。

次に解答例としてあった二つの実装パターンをご紹介します。

static String sort(String s){
        char[] content = s.toCharArray();
        java.util.Arrays.sort(content);
        return new String(content);
    }
    
    static boolean permutation(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        return sort(s).equals(sort(t));
    }

static boolean permutation_2(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        
        int[] letters = new int[256]; //文字コードの仮定;
        
        char[] s_array = s.toCharArray();  
        for(char c:s_array){
            letters[c]++;
        }
        
        for(int i=0;i<t.length();i++){
            int c = (int)t.charAt(i);
            if(--letters[c] < 0){
                return false;
            }
        }
        return true;
    }

１個目はsortメソッドを作成し、二つの文字列を整列してから比較しています

２個目のメソッドは文字コードのリストをboolで作って出現したら1に、二個目の文字列を判定して、存在したら-1して0より小さくなったらその時点でfalseというのは面白いですね。

比較結果

メインメソッドを以下のように実装し実行時間を計ってみました。

public static void main(String[] args){
        long start = System.nanoTime();
        MyisAnagram("word","wo rd");
        MyisAnagram("word","fugafuga");
        MyisAnagram("word","rdow");
        long end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation("word","wo rd");
        permutation("word","fugafuga");
        permutation("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation_2("word","wo rd");
        permutation_2("word","fugafuga");
        permutation_2("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
    }

結果は以下のとおりになりました

MyisAnagram(自分の実装)	permutation(解答例１)	permutation_2(解答例２)
13927ns	226304ns	5590ns

自分のは２位でしたね。悔しい。やはり全て足し合わせてから比較して結果を返すのと、比較しつつ結果を返すので差がついてしまったのでしょうか。解答例１の方はコードもスマートでしたがやはり関数呼び出しが入る分遅くなってしまったのでしょうか。

文字列操作を弄るのは楽しいですね。次回もまた何かプログラムを載せると思います。なにか御指摘ありましたら是非お願いします。

今月はまさかの２回更新できました。すごい

2017-01-10

C言語のポインタインクリメントの話

プログラミング

新年あけましておめでとうございます。今年は特に勉学への時間を費やしたいと思います。

さて、最近は競技プログラミングというか一からプログラミングとコンピュータの仕組みについて改めて勉強しているので今回はそこでふと疑問に思った点について書いてみました。

それはC言語のポインタの仕様です。

仕様というよりはコンパイラの解釈の方なのですが・・・　なにはともあれまずは次のCで書いたソースをご覧ください

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void A_reverse(char *str);

int main(void){
  char str[] = "abcdef";
  A_reverse(str);
  return 0;
}

void A_reverse(char *str){
  char* first=str;
  char* end=str;
  char tmp;
  int i,count=0;
  if(str){
    while(*end){
      ++end;
    }
    --end;

    while(str<end){
      tmp = *str;
      *str++ = *end;
      *end-- = tmp;
      count++;
    }
    printf("%s\n",first);
  }
}

このソースコード、まぁ読めばわかると思いますが文字列を逆に置換するものです。

str[]に文字を設定し、A_reverseメソッドでポインタを張り替え置換します。

ここで何が引っかかったかというと

while(str<end){
      tmp = *str;
      *str++ = *end;
      *end-- = tmp;
      count++;
    }

このループ部分の

*str++ = *end;
*end-- = tmp;

この辺りです。まず、strには文字列の先頭のアドレスが、endには文字列の終端が格納されています。 endは上の処理でヌル文字の一個手前のアドレスを指すようにしています。(今回の文字列をわかりやすくすると'[a][b][c][d][e][f][¥0]'でendは'[f]'を指します)

そしてもう一つ説明としてこの処理が属するwhileループは先頭と終端からお互いのアドレスを張り替えていき、中央で張り替えを中止します。

a b c d e f str→a end→f

↓

f b c d e a str→b end→e

↓

f e c d b a str→c end→d

↓

f e d c b a

↓

strのアドレスがendより大きくなったのでここで終わり！

となっています。この張り替えの処理が

      tmp = *str;
      *str++ = *end;
      *end-- = tmp;

です。

その時重要なのがポインタ演算子の評価順です。

上記のソースの *str++ = *end の部分ですがこれだけパッと見ると、strをインクリメントしたアドレスにendのアドレスを代入する　って僕は思ってました。

ですが、実際には

strの指すアドレスの内容をendのアドレスの内容に変更　→　strインクリメント　という流れらしいです。ややこしい

しかも最初のstr書き換えた後にstrをインクリメントしたらそれってendのアドレスから一個進むってことじゃねえの？って思ったら、なんと*str++と書くことでインクリメント前の値を取り出して参照変更して複写、そしてアドレスをインクリメントするそうです

なんというかスマートなコードではありますが少しわかりづらいので結構議論のタネになったりするそうです。

こういう記法は後置記法というそうで、*++strというような前置記法もできます。

この場合はインクリメントしてから値を取り出すという処理のようです。

これはコーディング問題の一つだったのですが思わぬ落とし穴があったので取り上げてみました。

ちなみにこれ以外にも落とし穴はあってメイン関数で宣言している　str[]　を　*strで宣言したりするとプログラムがBus error 10という忌まわしい文字を吐いて落ちます。

というわけでC言語を書き始めて３年以上が経っても未だに嵌る時は嵌るといったものでした。１時間ぐらい調べました。恐るべしポインタ。

大学の授業ではそこまで詰まった記憶はないのですがやっぱりまだまだ詰めが甘いですね。常に精進しろというお達しだと思ってがんばります。

それでは今回はこの辺りで筆を置かせていただきます。

2016-12-12

SECCON2016に少しだけ参加

土日に開催されたSECCON2016に素人ながら参加したので少しだけ解けた問題について

writeupなんて言うほどでもないのでタイトルにはつけてないです

Vigenere

 Vigenere

k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ

k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe

 |ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
-+----------------------------
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
B|BCDEFGHIJKLMNOPQRSTUVWXYZ{}A
C|CDEFGHIJKLMNOPQRSTUVWXYZ{}AB
D|DEFGHIJKLMNOPQRSTUVWXYZ{}ABC
E|EFGHIJKLMNOPQRSTUVWXYZ{}ABCD
F|FGHIJKLMNOPQRSTUVWXYZ{}ABCDE
G|GHIJKLMNOPQRSTUVWXYZ{}ABCDEF
H|HIJKLMNOPQRSTUVWXYZ{}ABCDEFG
I|IJKLMNOPQRSTUVWXYZ{}ABCDEFGH
J|JKLMNOPQRSTUVWXYZ{}ABCDEFGHI
K|KLMNOPQRSTUVWXYZ{}ABCDEFGHIJ
L|LMNOPQRSTUVWXYZ{}ABCDEFGHIJK
M|MNOPQRSTUVWXYZ{}ABCDEFGHIJKL
N|NOPQRSTUVWXYZ{}ABCDEFGHIJKLM
O|OPQRSTUVWXYZ{}ABCDEFGHIJKLMN
P|PQRSTUVWXYZ{}ABCDEFGHIJKLMNO
Q|QRSTUVWXYZ{}ABCDEFGHIJKLMNOP
R|RSTUVWXYZ{}ABCDEFGHIJKLMNOPQ
S|STUVWXYZ{}ABCDEFGHIJKLMNOPQR
T|TUVWXYZ{}ABCDEFGHIJKLMNOPQRS
U|UVWXYZ{}ABCDEFGHIJKLMNOPQRST
V|VWXYZ{}ABCDEFGHIJKLMNOPQRSTU
W|WXYZ{}ABCDEFGHIJKLMNOPQRSTUV
X|XYZ{}ABCDEFGHIJKLMNOPQRSTUVW
Y|YZ{}ABCDEFGHIJKLMNOPQRSTUVWX
Z|Z{}ABCDEFGHIJKLMNOPQRSTUVWXY
{|{}ABCDEFGHIJKLMNOPQRSTUVWXYZ
}|}ABCDEFGHIJKLMNOPQRSTUVWXYZ{

最初に解いたのはヴィジュネル暗号。なんだけどこれ普通にpをmd5でハッシュ化してるので演算ツールにハッシュ値を入力して逆演算させればFLAGが出てきた本当はキーをプログラム書いて特定して復号するのが正解なのかな？

VoIP

２問目はVoIP

VoIP
Extract a voice.
The flag format is SECCON{[A-Z0-9]}.
voip.pcap

パケットのキャプチャファイルが手に入るのでwiresharkで開くとRTPパケットが沢山。シーケンスから音声データに戻すと英語でフラッグを喋っているので聞き取ってFLAGを獲得、のはずがフラッグ部分の SECCON{9001I??}となって最後の２文字が何回聞いてもZAにしか聞こえなかった。orz

正解はSECCON{9001IVR}だったらしい…

basiq

basiq
What is admin's password?☺
http://basiq.pwn.seccon.jp

adminの本当のパスワードは何かという問題。パスにadminと追加して入力するとbasic認証が出てくる。SQLインジェクションの問題かな？って思ったのでpasswordに ' or 'A'='A'と入力したら入れたけど多分違う。結局FLAGまでたどり着けず時間切れ。この問題１００点なのに解けてるチームかなり少なくてビックリ。他の参加者の方のwriteupに期待

pwnとかexploitとかも解いてみたかったけど全然わからなかった！もっと色々勉強しようと思います><

2016-12-06

SC試験受けてきました

情報セキュリティ

次は認証に関する話の続きと言ったな　あれは嘘だ　

1か月以上空きました。色々勉強してたらなんか更新するの忘れてました。

さて、10月16日に情報処理技術者試験があったので自分は兼ねてより勉強（）していた情報セキュリティスペシャリストの区分で受けてきました。

ちなみに自分は基本も応用も持ってません。そこの知識は必要ですが資格として欲しいわけじゃないしSCしか眼中になかったので…

端的に言って結果としては落ちたと思います。怖いので自己採点はしてません。結果が公表されてからしっかり反省しようと思うので許してください。

一応今回の自分の受けた感想を書いておきます。

午前１

相当広い知識範囲を問われます。基本情報から応用までの知識がかなり比重として重いなと思いました。正直ここら辺での経営とかの知識はほぼ参考書チラ見程度だったのできつかったです。所感としてはギリ6割いってるかな？って感じでした

午前２

セキュリティ関係の知識がたくさん問われます。時事ネタも多少。自分としてはこっちの方がしっかり解けた感じしました。多分7割程度

午後１

セキュアプログラミングや組み込みシステムのネットワーク管理、プロキシサーバを主題として社内ネットワークのマルウェア感染時の対応のうちから2つ選んで答えます。自分はヒープオーバーフローに関するセキュアプログラミングとマルウェア感染の対応について答えました。こちらは記述の当たり方によるのでなんとも言えません。運よく6割いってないかなー

午後２

ICカードを用いた認証システムに関する問題と社内の脆弱性対策についての問題です。過去問は結構解いたのですが今までにない傾向の午後２だったので正直問題見たときは「詰んだ」って思いましたねどっちもきつかったですが多少知識のある認証問題を選択しました。こちらも記述次第ですね…

まとめ

基本的にセキュリティというのはそれ一つで大きな分野としてあるものではなく、情報分野の様々なところにセキュリティは存在していて、それをまとめて情報セキュリティと呼んでいるだけだと思っているので広い知識分野が必須だと自分は考えています。

もちろん、例えばソフトウェアのセキュリティに関して言えばプログラミング言語の仕様、バイナリやCPUの命令セットの仕組み等まで把握してないといけません。ハードやリアルな面で言えば経営の仕方、情報セキュリティ教育の方針等枚挙に暇がありません。とどのつまり広く深く知識がないとセキュリティスペシャリストとは言えないというわけでしょうね。

SCの試験については春にもう一度受けてみようかなと思いますがほかのこともあるので3か月前になったらもう一度考えてみます。 TOEIC等もあるのでそちらの勉強も疎かにはできないのが辛いです。

最近自分は暗号技術やリバースエンジニアリングの勉強を主にしていますがそれだけではダメ。ですが全部を極めるのはどう考えても難しい。ならば取捨選択は必須ということなので改めて自分のやりたいことは何なのか、それを考えるいい機会にもなったと思っています。進路を決定する時期にもなってきたので自分との会話をしっかりしてみようと思います。

それでは今回はこの辺りで筆をおかせていただきます。

次からはCTFとかで使う技術に関して書いてみようか…

2016-09-20

情報セキュリティにおける認証

情報セキュリティ

　今年の夏休みは十年来の友人に連絡が取れたりドラクエ夏祭りに参加したりと中々充実していた気がします。

さて、今回は現代のインターネット、情報システムにおいて当たり前のように使われている認証技術についてまとめてみました。

認証って？

認証：「一定の行為や文書の作成が正当な手続きによってなされたことを定められた公の機関が証明すること」（出典：松村明編『大辞林　第2版』三省堂）

らしいです。堅苦しいですが、情報セキュリティにおいての認証には二つの要素が含まれています。それが、Authentication　と　Certificationです。

Authentication
主にユーザーID、パスワード、もしくは生体情報などを用いて人、物、情報を識別し、その正当性や真正性を直接確認することです。通常は何らかの情報資産やシステムリソースなどへのアクセス権を管理し、アクセス制御を行っているシステムや人間と、それらに対するアクセスを要求するものとの間で直接的に認証行為がおこなれます。なのでこのような認証の方式を二者間認証という場合もあるそうです。

Certification
デジタル証明書による認証に代表されるような認証局などの第三者が発行する証明書の保有をもとにその持ち主の正当性を確認すること。つまり、この方式では認証が欲しい人、それを認証する人、そしてそれに介在すいる第三者（登録管理者なんて呼ばれてます）によって認証行為が行われます。こういった場合三者間認証なんて呼ばれるそうです。辞書に載っている方の認証に近い意味を持つのはこちらでしょうか？
「単位を教授に認めてもらう」なんていうのもCertificationに近いでしょうね（白目）

認証の分類について

先程述べたAuthenticationについて認証の対象を人、物、情報の三つに大別していました。その内容と具体例を調べてみました。

認証の種類	内容	具体例
人の認証	個人の識別を行い、事前に登録されている本人であることを確認すること	ユーザーIDとパスワードによる本人認証、指紋認証
物の認証	システムやネットワークへのアクセスを要求している機器などの正当性を確認すること	MACアドレスによる端末の認証、発信元電話番号による端末の認証
情報の認証	情報が不正に改変されていないことを確認すること	メッセージダイジェストやディジタル署名によってプログラムやデータの改ざんの有無を確認\|

所有物（ICカード、磁気カード）や秘密情報（パスワード、暗証番号）などによる認証は導入が容易で誰もが理解できるが単体で用いる場合によっては、実装や運用によってむしろセキュリティの低下につながる恐れがあります。そのため、高度なセキュリティが求められる環境やシステムなどでは二つを併用する、もしくはバイオメトリクスによる認証が用いられることが多いそうです。典型的な例としては、キャッシュカード（所有物）と暗証番号（秘密）によって本人認証を行い、銀行からお金を引き出すといったものがあります。こういった方式を二要素認証もしくは多要素認証と呼びます。

ちなみに、非常に破られにくい生体認証（バイオメトリクス認証）ですが導入のコストが非常に高いのでそこらかしこに導入するというのが出来ないのがデメリットです。

次の記事からは色々な認証方式についてまとめてみようと思います。

それでは今回はこの辺りで筆をおかせていただきます。

2016-09-13

インターンに行ってきました。

二週間ほどガッツリ二社のインターンに行っていたので中々記事書く暇ありませんでした

IBM
　こちらは五日間ほど、誓約書の関係でどこまで書いていいのかわからないのでふわっと所感を。
一言でまとめると「すごい」　小学生並の感想ですがまさにこの一言に尽きます。
　さすが100年の歴史を持つ老舗といったところでしょうか。IT分野を利用しての様々な新規分野への開拓はこれからITがエコシステムとして成り立っていく可能性をしっかりと感じました。
自分はコグニティブやらワトソンやらがいまいちよく分かっていなかったので非常にタメになるお話ばかりでメモばっかとってました（笑）　あと英語、これはできないとダメですね！（TOEIC400点ぐらい）
　社員の方々も知識、技術素晴らしい方々ばかりでお話も大変参考になりました。X-Force,SOC、面白そうです…ｼﾞｭﾙﾘ　自分はセキュリティコースでしたが他のコースも非常に面白そうでした。同じチームの人たちは分野は違えど同じ「セキュリティ」に興味を持つ者同士が集まったという感じですごく良い刺激になりました。docker等の仮想化技術を利用しての新しい知見を得られたのでこれからしっかり勉強していこうと思います。モチベーションをグングン上げさせてもらいました。企業のセキュリティポリシで社内が全て撮影禁止だったので写真が一枚もないので頭の中でしか振り返りができないのが少し残念です。

サイボウズ
　IBMのインターンは全コース合わせて100人ほど居たので、もしかしたらまたそんなに沢山居るのかな？なんて少しビビりながら日本橋のオシャレなオフィスに行くと自分も含めて8人、遠隔地の方合わせて10人とビックリしました。逆になんで自分が受かったのかは最終日まで甚だ疑問でした。
同じ参加者の皆さんは凄く気さくな方たちでお話ししていてすごく楽しかったです。初日に武田玲奈さん似ているという社員さんが居ると聞いて同じ参加者の方と即座に社内を物色していました。ただの変人ですね。

大体のガイダンスが終わるとすぐに業務（とほぼ同じ体験）をさせていただき初日から濃密でした。
こういう大手のインターンって大体は業務の紹介とか見学でほぼ終わることが多いと聞いていたのですごく新鮮で参考になりました。
お会いする社員さんも皆さん素晴らしい人達ばかりでお話ししていてすごく楽しかったです。一番びっくりしたのは人事の方との面談で僕がポロット「マーケティングとかも面白そうって感じるんですよね」と漏らしたら次の日にはBPMの偉い方との面談が組まれていました（汗
ちなみにBPMの方とお話していたら「youtuberの方ですか？笑」って言われました。そんなに胡散臭い喋り方をしていたんでしょうか…
他にもプログラマーの方でwebアクセシビリティに詳しい方とデザインの方を交えて熱いお話を繰り広げさせていただきました。
幼いころから障碍者の方と触れ合う機会が多かったので凄く興味をそそられました。実際話してる最中暑かったのか汗かいてました。
ちなみに最後、5日間のまとめとしてプレゼンがあって、ネタに走っていいよと言われたので普段学校でできないようなプレゼンをしたらドン引きされたり苦笑されたりしました。それでも一部の人は「面白かった」、「予想の斜め上を行ってくれた」と仰っていただき救われましたね
そんなこんなであっという間の5日間でした。
【総括】

今年のインターンは大手の2社に受かるというラッキーを発揮し、来年の就活が少し不安になってきましたが得るものはこの2、3年で最も大きいと言っても過言ではなかったと思います。

他にも企業見学等はこれからも行う予定ではありますが、たった2社見ただけでも色合いが凄く違う。それはもう面白いぐらいに。友人のインターンの話を聞いていても面白いです。そろそろ自分の志望も固まってきたのでこれからもしっかり勉強、たまに息抜きしてしっかり精進していきたいと思います。

そろそろ木曜から学校も始まるので単位を落とさないようにしないといけませんね。それでは今日はこの辺りで筆をおかせていただきます。

サイボウズの人事は綺麗な方が沢山でした

SWEet

A Software Engineer Is Eating Technologies