るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

参照カウンタオーバーフローを利用したLinuxカーネルエクスプロイト(CVE-2016-0728)

本記事では、Linuxカーネルの鍵保存サービスの脆弱性(CVE-2016-0728)、およびそれを利用した権限昇格エクスプロイトについて解説します。 Linuxカーネルの参照カウンタオーバーフローはCVE-2016-0728とCVE-2014-2851が有名ですが、今回は前者を題材に扱いま…

低レイヤーの歩き方

この記事は Kobe University Advent Calendar25日目の記事です。低レイヤー技術(後述)をこれから学びたい人向けの入門記事です。 自身の経験を踏まえ、より多くの人達にこのレイヤーに興味を持ってほしくて書きました。 決して卒論がやばくてAdvent calendar…

高機能バイナリトレーサqiraはどのように実装されているのか

1. qiraとは qiraとは世界的なハッカー、George Hotz氏 (ジョージ・ホッツ - Wikipedia) によって開発された高機能バイナリトレーサーであり、qiraという名は(QEMU Interactive Runtime Analyser)の略である。GitHub - BinaryAnalysisPlatform/qira: QEMU …

OSC2016 Kyoto 参加報告

前回のOSC Tokyo Springに続き今回の OSC 2016 Kyoto(2016年7月29日-30日) オープンソースカンファレンス2016 Kyoto - オープンソースの文化祭! にも参加してセミナー発表、展示をさせていただきました。ので参加記を書きます。今回も前回に引き続き、去年…

弾幕ゲー開発用スクリプト言語を自作した話

なんとなくスクリプト言語を作ってみたくなったので、東方のような弾幕ゲーで敵の行動,弾幕パターンを記述するためのスクリプト言語を作ってみました。 (最近のゲーム業界ではわざわざDSLを作るより、LuaやHaxeのような汎用的なスクリプト言語と組み合わせる…

OSC2016 Tokyo/Spring 参加記

OSC 2016 Tokyo/Spring オープンソースカンファレンス2016 Tokyo/Spring - オープンソースの文化祭! に参加してセミナー発表、展示をさせていただきました。ので参加記を書きます。今回は、去年の8月に行われたセキュリティ・キャンプ2015全国大会の有志メ…

KVMのなかみ(KVM internals)

VMMの高速化について学ぶ過程でKVMのコードを読んだので、 メモ代わりに内部構造の解説記事を書きました。KVMはqemuと連携して動作するため、以前私が書いたQEMU internals( http://rkx1209.hatenablog.com/entry/2015/11/15/214404 ) も合わせてご参照くだ…

Intel GVT-gにみるMediatedパススルーを用いたGPU仮想化

この記事は システム系論文紹介 Advent Calendar 2015 - Adventar 17日目の記事です。 USENIX'14 ATCにてintelのKun Tian, Yaozu Dong,David Cowperthwaiteによって発表され、XenGTやKVMGTとしてごく最近に実装された新しいたGPU仮想化方式、GVT-gについて見…

パイプラインモデルを用いたシンボリックテイント解析の高速化

この記事は情報セキュリティ系論文紹介 Advent Calendar 2015 - Adventar9日の記事です。 TaintPipe: Pipelined Symbolic Taint Analysis [Ming,et al. USENIX SEC' 15] https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-ming.…

SEGVという概念が存在しない退屈な世界

この記事はKobeUniv Advent Calendar 2015 - Adventar12/6の記事です。本カレンダーではKobeUniversityの現役生または卒業生が自分のやっている事(技術系,理工系に限らず) について自由に書く物です。すごい身内ネタで終わってしまうと思っていましたが予想…

QEMUのなかみ(QEMU internals) part2

前回(part1)rkx1209.hatenablog.com の続きです。part2では仮想IRQ,チップセット,仮想IO,TCGを見ていきます。 多分part2で終わりです。(時間があればまたいつかpart3とか書いてみたいですね...)ではまず仮想IRQから見ていきます。6.仮想IRQ QEMUにおいてIRQ…

QEMUのなかみ(QEMU internals) part1

ここ一ヶ月ほどQEMUのコードとお戯れしていたのですが、qemuのソースコードもうすぐ読みきりそうなのでどこかにまとめたいんだけど、qemu internalみたいな記事ってどれぐらい需要あるの— 前代未聞 (@RKX1209) 2015, 11月 9と言ってみた所なんとなく需要があ…

2014年の振り返り

2014年ももうすぐ終わるので、一年を振り返ります。 (こうでもしないと何やってたかすぐ忘れるので...)2014年 [1月] 集合論とか位相の勉強してた気がする。まだ数学やってた [2月] レンダリングとかアニメーションとかのコード書いてた 3Dゲーム作った気がす…

30日でできない 自作Linuxクローン開発

この記事は 自作OS Advent Calendar 2014 - Adventar 12/25の記事です。一ヶ月程前からLinuxカーネルのコードを読み始めたので、解読ついでに自分でもカーネルを作ってみました。 とはいっても、まだ半分も完成してないです() 当初は、30日でできる 自作Li…

セキュリテイキャンプ2014 参加記

8/12~8/16に行われたセキュリティキャンプ2014に参加しました。 クラスはソフトウェアセキュリティクラスです。以下参加記。[1日目] 何とかして会場に着く。みんな結構早くついていて、すでにたくさん人がいた。 とりあえずいろんな人と名刺交換をする。首…

Debug Interface Access SDKを使って内部関数の名前解決を行う

IDAを使ってソフトウェアの解析をしてるといつも思うんですが、デバッグ情報って便利ですよね。IDAはイメージファイルをロードした後にpdbの検索も行っていて、シンボル情報とかのラベルを自動で埋め込んでくれます。これがあるおかげで、アセンブリをあまり…

RPGのようななにか

RPGのようななにかを作りました。 ソースはここにおいてあります RKX1209/java-RPGTest · GitHub 本体はこちらからダウンロードできます https://dl.dropboxusercontent.com/u/33821276/RPGTest.jar~プレイする前に読んでください~(操作説明) 矢印キー....…

あけましておめでとうございます

もう1/2ですが、 あけましておめでとうございます。去年はいろいろと悲惨な年だったので今年は頑張りたいですね。新年の目標はあまり具体的には決まっていないので、おおまかに書きます。2014年の目標(笑) ・東大出版の基礎数学シリーズを読了する ・岩波現…

2013年の振り返り

少し早いですが、今年の振り返りをしようと思います。1年前の今頃はこんな記事書いてました。あけましておめでとうございます - るくすの日記 ~ Out_Of_Range ~この時はまだ、競プロ一直線みたいな感じだったんですが..... 今はと言うと、うーん... どうして…

作図問題についてあれこれ

この記事は数学 Advent Calendar 2013 - Qiita [キータ] 12/24の記事です。 こんにちは。久しぶりのブログ更新です。最近、開発やら競プロやらをほっぽり出して 数学ばかりやっています。数学AdventCalendar24日目という事で、今日は作図問題について書こう…

ζ(4)の計算

たまには数学関係の事でも書こうかな~。しかしダラダラと定義やら証明やらを書き連ねるのも面倒なので、比較的簡単な計算問題について書きます。 今回はζ(4)の計算。ゼータ関数とはで表される関数ζのことです。つまりζ(4)はで表される級数の事です。 では収…

文字列でダンガンロンパOP やってみた

こんな動画を見つけたので↓ 私も某アニメのOPでやってみました。ようつべに上げてます↓ (ちょっと目に悪そうなので回覧注意です) 文字列でダンガンロンパ OP - YouTube OpenCVを使ってゴニョゴニョした後、JavaScriptに埋め込んで連続再生させてるだけです。…

ライフゲーム作ってみた

先日観ていた動画にこんな物がありました。 ライフゲームの世界【複雑系】 ‐ ニコニコ動画:GINZA 一応ライフゲームの存在は以前から知っていたのですが、ここまで奥が深いとは.... 動画を観ている内に、自分でもやってみたくなったのでソフトを作ってみまし…

情報科学概論のアレ

情報科学概論のロボットの問題を解きました。 とりあえずプログラム書いてPCに計算させます。(ゴリ押しですが何か)アルゴリズムは愚直に幅優先探索。(6台までは30秒ぐらいで答えが出る。)ロボットが1~6台の時の最短方法は以下のようになりました。台数 手順 …

AOJ 0041 Expression

AOJ

[問題文] AIZU ONLINE JUDGE [解法] 構文解析 + 全探索 めんどくさそうだったので放置してた問題。カタラン数C[3] = 5なので、括弧のつけ方はすべて列挙しても問題ない。あとは数字の並び 4! 通りと 演算子 3^3 通りと 括弧のつけ方C[3]通りを試して構文解析…

SRM 563 Div2 hard SpellCardsEasy

[問題文] TopCoder Statistics - Problem Statementカードの並びが与えられる。カード[i]にはlevel[i]とdamage[i]が書いてある。カード[i]を選んだとき、相手にdamage[i]のダメージを与え、カード[i]よりも右に置いてあるカードlevel[i] - 1枚を取り去る。(…

AOJ演習

AOJ

最近、理論固めやバイトで忙しくて問題をほとんど解いていなかったのでひさしぶりにAOJ。 最近追加されたPCK2012予選過去問を解きました。 AOJ256(PCK 1): 10問解いたら何点取れる? AIZU ONLINE JUDGE 書くだけ int main(){ int sum = 0; rep(i,10){ int tm…

あけましておめでとうございます

あけましておめでとうございます。(もうすぐ1/2ですが)正月といえば書初め(コード)ですね。 確か去年の書初めはアセンブラで書きました。 今年は競技プログラミングをやっていく予定なので、普通にC++で問題を解こうと思いますw ~書初め~SRM555 Div2 255: …

2012年の振り返り

もうすぐ2012年も終わりですね。 ということで今年を振り返ってみようと思います。 ~ 2012年の振り返り ~ 1~3月 去年の冬頃から競技プログラミングをするか情報セキュリティをするか迷っていたが、前者を選ぶことに決める。 蟻本購入。 勉強しつつ、だらだ…

Dynamic Programming 演習(2)

前回(動的計画法(Dynamic Programming)演習 - るくすの日記 ~ Out_Of_Range ~)の続き。今回は該当するDiv2Hardのうち13問解きました。 [Div2](SRM354) 1000:UnsealTheSafe dp[i][j] := i-1番目にjを押すようなパスワードの総数 sum += dp[i - 1][keypad[ny][…

Dynamic Programming 演習

タイトルのまんまです。 TopCoder SRMの過去問から解法に「Dynamic Programming」が含まれている問題をレベルで昇順にソートして解いていきます。 該当するDiv2Medium全18問中15問解きました。(残り3問は、dpでふつう解かないだろうみたいな問題だったので別…

PKU 2112 Optimal Milking

PKU

[問題] 2112 -- Optimal Milking牛とミルクマシーン(適当)が辺で接続されている。全ての牛をミルクマシーンに到着させたい。この時もっともたくさん歩く牛の距離を最小化せせよ。ただし、ミルクマシーンはm匹の牛しか処理できない。 [解法] WarshallFloyd + …

PKU 1949 Chores

PKU

[問題文] 1949 -- ChoresN個の仕事がある。それぞれにかかる時間と、その仕事より必ず先に終わらせなければならない仕事k個の情報が与えられる。 仕事は並列で行うことができる。N個の仕事を終わらせるのにかかる時間を最小化せよ。 [解法] トポロジカルソー…

AOJ 1001 Binary Tree Intersection And Union

AOJ

[問題文] AIZU ONLINE JUDGE [解法] 構文解析 慣れていないのでかなり時間がかかった。 こんなやつの解析 <exp>::= "(" , <exp> , <exp> , ")" | "" 結構楽しい。 struct E{ int l,r,id; int over; E(){ l = r = -1 ,id = 0; over = 0;} }; int now; int p = 0; E memo[400]</exp></exp></exp>…

SRM 534 Div2

250: EllysDirectoryListingやるだけ class EllysDirectoryListing { public: vector <string> getFiles(vector <string> files) { int one = 0,two = 0,last = files.size() - 1; rep(i,files.size()){ if(files[i] == ".") one = i; else if(files[i] == "..") two = i; } </string></string>…

AOJ 1075 High and Low Cube

AOJ

[問題文] AIZU ONLINE JUDGE[解法] 実装 結構しんどい const int my_start_x[6] = {7,0,7,14,21,7}; const int my_start_y[6] = {0,7,7,7,7,14}; const int oji_start_x[6] = {36,29,36,43,50,36}; const int oji_start_y[6] = {0,7,7,7,7,14}; char C[10][7…

SRM 535 Div2

珍しく簡単なセットだった。250: FoxAndIntegers少し大きめにとった class FoxAndIntegers { public: vector <int> get(int AmB, int BmC, int ApB, int BpC) { vector <int> result; for(int a = -100; a <= 100; a++){ for(int b = -100; b <= 100; b++){ for(int c </int></int>…

SRM 536 Div2

250: BinaryPolynomialDivTwoやるだけ pow関数でTCのコンパイラがエラーを吐きまくって謎 class BinaryPolynomialDivTwo { public: int countRoots(vector <int> a) { int p = 0,p2 = 0; rep(i,a.size()){ p += a[i] * (int)pow(0.,i); p2 += a[i] * (int)pow(1.,</int>…

AOJ 1016 Fibonacci Sets

AOJ

[問題文] AIZU ONLINE JUDGE [解法] dp + UF木 数列を作っておいて、UF木で集合を作る。 int par[2000]; int rank[2000]; void init(int n){ rep(i,n) par[i] = i; memset(rank,0,sizeof(rank)); } int find(int x){ if(par[x] == x) return x; return par[x…

SRM 537 Div2

250: KingXNewBabyやるだけ const char vow[] = {'a', 'e', 'i', 'o','u'}; class KingXNewBaby { public: string isValid(string name) { int ex[100]; memset(ex,0,sizeof(ex)); if(name.size() == 8) rep(i,name.size()) ex[name[i] - 'a']++; int c = 0;…

SRM 538 Div2

300: LeftOrRight300にする必要あるかなあ...左にいってまた右にもどるみたいな操作は必要なさそうだったので、左と右のみに絞ったら通った。(証明はしていない) class LeftOrRight { public: int F(string s){ int res = 0; int now = 0; rep(i,s.size()){ …

SRM 539 Div2

250: PlatypusPaternity変なバグを出して時間がかかってしまった。 class PlatypusPaternity { public: int Can(string fm,string ms,string group){ int ret = 0; rep(i,group.size()){ if(group[i] == 'Y' && fm[i] == 'Y' && ms[i] =='Y') ret++; if(grou…

SRM 540 Div2

250: RandomColoringDiv2やるだけ class RandomColoringDiv2 { public: int getCount(int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) { int result = 0; rep(r,maxR){ rep(g,maxG){ rep(b,maxB){ int dr = abs(r - sta…

SRM 541 Div2

250: AkariDaisukiDiv2わーいSRMあかりSRM大好きー class AkariDaisukiDiv2 { public: int countTuples(string S) { int result = 0; for(int x1 = 0; x1 < S.size(); x1++){ for(int x2 = x1 + 1; x2 < S.size() - 1; x2++){ for(int x3 = x2 + 1; x3 < S.s…

SRM 543 Div2

250: EllysTSP訪れる順番は気にしなくて良いので、普通にやるだけ。 class EllysTSP { public: int visit(int s,string p){ int ret = 1; bool flag[100]; memset(flag,0,sizeof(flag)); int now = s; flag[s] = true; while(true){ bool update = false; re…

SRM 545 Div2

250: ANDEquationやるだけ class ANDEquation { public: int restoreY(vector <int> A) { int result; rep(i,A.size()){ int y = A[i]; vector<int>t; rep(j,A.size()){ if(j == i) continue; t.pb(A[j]); } rep(i,t.size() - 1) t[i + 1] = t[i] & t[i + 1]; if(t[t.s</int></int>…

SRM 546 Div2

250: ContestWinnerやるだけ class ContestWinner { public: int getWinner(vector <int> events) { map<int,int>mx; rep(i,events.size()) mx[events[i]] ++; int imx = 0; for(map<int,int>::iterator it = mx.begin();it != mx.end(); ++it) imx = max(imx,(*it).second); mx.cle</int,int></int,int></int>…

Googleに行ってきました

先日部で、2泊3日の東京遠征に行ってきました。 1日目は秋葉原、2日目は発表練習、そして3日目はGoogle社に訪問させていただきました。Google社では社内食堂で、かの有名な『Binary Hacks』の著者の方とお食事、お話させていただいた後、エンジニアの方々の…

SRM 548 Div2

250: KingdomAndDucks やるだけ int kind[100]; class KingdomAndDucks { public: int minDucks(vector <int> duckTypes) { memset(kind,0,sizeof(kind)); int k = 0; rep(i,duckTypes.size()){ if(!kind[duckTypes[i]]) k++; kind[duckTypes[i]]++; } int mx = 0</int>…

SRM 550 Div2

250: EasyConversionMachine無駄な操作を除いた必要最低限の回数に2回ずつの無駄な操作を追加してkにできればPOSSIBLE class EasyConversionMachine { public: string isItPossible(string originalWord, string finalWord, int k) { int need = 0; rep(i,or…