第一オペランドをA、第二オペランドをB、計算結果をRとする。
キャリー(加算) = A + B の繰り上がり (符号なしの時の繰り上がりを検知する)
キャリー(減算) = A + (~B + 1) の繰り上がり (符号なしの時の繰り下がり無しを検知する)
オーバーフロー(加算) = (MSB(A) ^ MSB(R)) & (MSB(B) ^ MSB(R)) (符号ありの時のおかしな符号を検知する)
オーバーフロー(減算) = (MSB(A) ^ MSB(B)) & (MSB(A) ^ MSB(R)) (符号ありの時のおかしな符号を検知する)
符号なしでも符号ありでも、CPUは上記の計算を行っているだけである。
しかし、符号なしは0x00や0xffで非連続であり、符号ありは0x7fや0x80で非連続である。
この性質により、キャリーフラグは符号なし、オーバーフローは符号ありでのみ意味を持つことになる。
fgets()について
fgets(s, sz, fp)と引数を取ったとすると、
fpが適切なファイルを指していない場合や、szに0を指定した場合、szがどんな値であったとしてもsの内容は変更されず、fgetsはnullを返す
fpが適切なファイルを指しており、szに1以上の値を指定した場合、sの内容は文字列+'\0'の形で変更され、fgetsはsを返す
特にszが1の場合、sには'\0'だけが入るので注意
elf32の実行形式の「lea 0x4(%esp), %ecx」とは何なのか？
elf32では、main関数の最初にespを16bitの境界にアライメントする。
これは、おそらくSSE命令などのペナルティを避けるためだと考えられる。
しかし、単に「andl $0xfffffff0, %esp」などとすれば、スタートアップ関数直後のespの値が失われてしまう。
これは、mainが終了した時にまずいことが起こるため(スタックがずれてしまう可能性が非常に高い)、ecxにespの値を退避しておく必要がある。
ちなみに、なぜかelf64では同等のコードは生成されない。
(追記)
配列の範囲を超えてデータを書き込むことによるバッファオーバーフロー攻撃を行う際には、このコードが邪魔になることがある。
というのも、espのコピーを保存したecxの値はスタックにpushされて保管されるため、バッファオーバーフロー攻撃によってこれが破壊されるからである。
ecxの値が破壊されてしまうと、mainの終了間際にespの値が復元できなくなるため、プログラムがクラッシュする。
これを避けるためには、逆アセンブルしたコードを読んでecxの部分をピンポイントで避ける必要があるが、これは本当に面倒である。
もしかしたら、このコードはセキュリティを意識したものでもあるのかもしれない。(でも、64bitでは生成されないんだよなぁ...)
elf64ではこのようなコードは生成されないため、脳死でリターンアドレスを書き換えるだけで攻撃が成功する。
pオプションとsetresuid()について
まず、権限下げがない場合について
ノーマルはX
pオプションはO
setresuidはO
pオプション+setresuidはO
次に、権限下げがあった場合について
ノーマルはX
pオプションはX
setresuidはO
pオプション+setresuidはO
/bin/shや/bin/bashを起動する際に、実UIDと実行UIDが異なる場合は、/bin/shや/bin/bashが実行UIDに実UIDをセットしてしまうのは本当。
→権限下げがない場合のノーマルはXなのに対して、権限下げがない場合のpオプションはOであるから
pオプションは/bin/shや/bin/bashの権限下げには対応できるが、ターゲットプログラム内の権限下げには対応できない
→権限下げがない場合のpオプションはOであるが、権限下げがある場合のpオプションはXであるから
setresuidは/bin/shや/bin/bashの権限下げと、ターゲットプログラム内の権限下げの両方に対応している
→権限下げがない場合のsetresuidも、権限下げがある場合のsetresuidもOであるから
つまり、setresuidを使えば、pオプションを使う必要はない
車輪の国 向日葵の少女 その1
まずは自己紹介をしよう。
おれは森田健一(もりた けんいち)。
SF小説と姉貴が大好きだ。
いつも読んでる本の中で『日本』という国が出てくる。
あんたも知っているかもしれないが、面白おかしくて不思議な島国だ。
なにが面白いかって？
例えば現実じゃあ、人を殺したら『一生子供を持てない』罪を背負うだろう？
そして『特別高等人』というおっかねぇ連中の保護観察を受けることになる。
でも『日本』は違う。
人殺しは首吊って殺されるんだそうな。
もしくは十年か、二十年か、はたまた一生かわからんが・・・。
とにかく刑務所ってトコに入れられる。
刑務所は牢屋とか監獄ともいうらしくて、おれたちの国にはないものだから面白い。
この刑務所ってのが曲者で、人殺しも盗人も痴漢親父も、みんなココに入る。
犯罪者のテーマパークみたいな感じかな。
もう少し軽い罪・・・車のスピード違反なんかは国に金を払えばいいらしい。
首吊りか、刑務所か、金か・・・。
おれたちの国には罪に応じた罰が多種多様に細かく定められているけれど、日本には大きく分けてこの三つしかないらしい。
そんなんでヒトが更生するのかって、おれたちなんかは思うだろう？
・・・まあ、逆に、人殺しに子供を持てないようにするだけで世の中は大丈夫なのかと、問い詰められたら怪しいもんだ。
利己的な遺伝子がどうとか、犯罪形而上学がどうとか、宗教的とか自己の対立とか言ってる頭の偉い人たちが決めた法律に、おれたちはなんとなく従っている。
・・・なんとなく・・・ってのは『日本』にいる人たちも一緒なんだろうな。
だから、もうすでに決まっている法律や制度については、おれもよく語れない。
問題は『日本』にしろ、この『国』にしろ、そんな世の中でどうやって生きていくのかと。
俺みたいなぺーぺーが、どうやって姉貴と愛を結ぶのかと、そういう話だ。
ー近い未来、そう遠くない場所ー
・・・。
後ろを振り返らずに歩くこと六時間。
田舎ってのは少なからずバスが通っているもんだ。
ど田舎じゃあ、いい感じの爺さんがトラックの荷台に乗せてくれるかもしれない。
だが、おれの故郷は、田舎というよりむしろ秘境。
数学的帰納法ってなに？数学的演繹法はないの？
数学的帰納法はn=1のときに成り立つことを調べて、n=mのときに成り立つことを仮定してから、それが実はn=m+1のときでも成り立ちますということをするやつです。(語彙力)
簡単に解説すると、数学的帰納法では任意のmでの成立を仮定しますが、そのn=mのmの部分には1も含まれます。
それがn=m+1のときにも成り立つことがわかったのであれば、すでにn=1のときの証明はされているはずなので、とうぜんn=1+1のときや、n=1+1+1のときの証明もされていくことになります。
数学的演繹法は普段からみなさんがやっているやつで、AならばB、BならばC、Cならば...という風に、論理立てて証明していく方法です。
じゃあ、数学的帰納法は論理的じゃないのか！？とおもわれるかもしれませんが、はじめに立てる仮定(n=mのとき云々)以外は演繹法そのものなので安心してください。
n=1からはじめて、nが限りなく大きな自然数になるまでドミノのように証明されていくようすから、数学的帰納法という名前がつけられたみたいです。(でも、あんまりしっくりこない)
線形代数の個人用メモ
はじめにお断りしておくと、数学を今までサボっていたせいで僕はあまり数学には詳しくないです。
すごく悲しいです(真顔)
【行列式を調べることでなぜ方程式の解について調べることができるのか？】
行列式が0の場合は方程式の解は不定・不能となり、行列式が0でない場合は方程式の解は一つに定まる。
実は、行列式が方程式に解に関わってくる理由は、方程式を普通にといたときに分母に行列式が出てくるから。
二次方程式をすべて文字で置いてxやyについて変形してみると、その意味がわかると思う。
【正方行列に特有の性質など】
・行列式は正方行列のみ定義される
・逆行列も正方行列のみ定義される
・正則行列(rank = n、言い換えると逆行列を持つ行列)は正方行列のみ定義される
・固有値や固有ベクトルは正方行列についてのみ定義される
【固有値や固有ベクトルの求め方】
そもそも、固有値・固有ベクトルの性質として「ある行列Aについて、Ax=λxが成り立つ」がある。
言い換えると、ある行列Aに作用させてもその方向が変わらないベクトルが行列Aの固有ベクトルであり、その倍率が固有値である。
次に、Ax=λxを変形すると(λE-A)x=0と書くことができる。
xは固有ベクトルであり、ゼロベクトルでないので、det|λE-A|=0となる。
これは、det|λE-A|が0以外の値だと(λE-A)は逆行列を持つことになり、自明な解としてxはゼロベクトルになってしまう。
det|λE-A|=0を解くと固有値λが求まるので、各固有値を(λE-A)x=0の式に代入して固有ベクトルを計算する。
こうすると、各固有値に対して少なくとも一本以上の固有ベクトルが取れる。
det|λE-A|のことを固有多項式といい、det|λE-A|=0のことを固有方程式という。
更に言うと、固有ベクトルの計算の際には解は必ず不定性を持つ。
これは、det|λE-A|が0であり逆行列を持たないので、解はそもそも一つに定まらないことと、右辺の定数項ベクトルが0ベクトルの場合は方程式は必ず解を持つので、不能ではないことが理由である。
解が一つに定まらず、不能ではないとなれば、不定になることになる。
他の直感的な解釈としては、固有ベクトルxを2倍したものも行列Aの固有ベクトルになっている。
A(2x)=λ(2x)は実際にxに2xを入れたもの。
ある固有ベクトルを定数倍したものも行列Aの固有ベクトルになるのであれば、固有ベクトルは不定性を持つことになる。
一つの固有値に対して固有ベクトルは一つだけではなく、長さを変えたものも固有ベクトルだということだ。
あと固有ベクトルの計算における注意点として、固有ベクトルをsという変数で定数倍する際に使用する変数は0でないという条件をつけるのを忘れずに！！
豆知識として、固有ベクトルを配置する順番を変えると、結果として得られる対角行列の中の固有値の並びの順番が変化する。
変換行列のとり方はたった一つだけではないということに注意。
【一次独立な固有ベクトルxを並べた行列p={x1, x2, ... xn}が逆行列を持つことの証明】
c1x1 + c2x2 + ... + cnxn = 0を考えた時、この式はc1~cnが未知数の方程式だと考えられる。(x1~xnを行ベクトル、c1~cnを列ベクトルとして掛け算する)
ここで、p={x1, x2 ... xn}が逆行列を保つ場合はc1~cnは0の自明な解を持つが、それ以外の場合はc1~cnが0以外の解を持つ可能性がある。
これはxが一次独立であることに矛盾するので、pは逆行列を持つ。
まぁ、一次独立なベクトル並べてる時点で、逆行列を持つことはわかるんだけどね。
【p^-1Apが対角化されることの証明】
p^-1Ap = p^-1(Ax1 Ax2 .. Axn) = p^-1(λ1x1 λ2x2 .. λnxn) = p^-1p[λ1からλnを対角線上に並べた行列]
ここでp^-1pはEであるため、右辺が対角化行列になり証明完了。
ちなみに、対角化された行列は固有ベクトルを対角線上に並べたものになる。
【n次正方行列Aにおいて、異なる固有値λ1, λ2 .. λkに対する固有ベクトルx1, x2 .. xkは一次独立であることの証明】
①k=1の時、固有ベクトルは一本しかないので成立は明らか
②k=mの時、成立を仮定すると
c1x1+c2x2+..+cmxm+cm+1xm+1=0 (これを式1とおく)
式1の両辺に左からAをかけると、c1Ax1+c2Ax2..+cmAxm+cm+1Axm+1=c1λ1x1+c2λ2x2+..+cmλmxm+cm+1λm+1xm+1 (式2)
式1の両辺にλm+1を掛けた後、式2からその式を引くと、c1(λ1-λm+1)x1 + c2(λ2-λm+1)x2 + ..... + cm(λm-λm+1)xm = 0 (式3)
ここで、x1~xmは一次独立だと仮定しているので、式3においてci(λi-λm+1) = 0 (i = 1, 2, ... m)が成り立たねばならない。
ここで、固有値λ1~mはすべて異なるとしているので、λi-λm+iはすべて0でない数になる。
すると必然的にciが0になる。
c1~m = 0を式1に代入すると、cm+1xm+1=0となり、xm+1は固有ベクトルで0ベクトルでないので、cm+1も0となる。
以上より、x1~m+1はすべて一次独立。
