除算演算逆解析

除算演算逆解析

除算演算逆解析

関連数学公式

除数2のべき乗

除数が負の2のべき乗

除数非2のべき乗

除数が負の非2のべき乗

除法命令の命令周期が長く,効率が低いため,コンパイラは除法命令の代わりに他の命令の組み合わせを工夫した.そこでC/C++除算演算の逆解析は他の演算よりも複雑であることをまとめた.
相関数式
b>0の場合、
⌊ab⌋=⌈a−b+1b⌉
さらに
⌈ab⌉=⌊a+b−1b⌋
b<0の場合、
⌊ab⌋=⌈a−b−1b⌉
さらに
⌈ab⌉=⌊a+b+1b⌋
1.除数2のべき乗
sar命令は下向き整列,すなわち⌊x 2 n⌋に相当し,C言語除算結果はゼロ方向整列,すなわち[x 2 n]である.次のようになります.
[x2n]=⎧⎩⎨⎪⎪⎪⎪⎪⎪⌊x2n⌋⌈x2n⌉=⌊x+2n−12n⌋x≥0x<0
次に例を示します.

//.c
printf("nVarOne/8=%d",nVarOne/8);

コンパイル後の逆アセンブリ:

;.asm
 mov    eax,dword ptr [ebp-4]
 cdq
 and    edx,7
 add    eax,edx
 sar    eax,3
...

and edx,7は、nVarOneが負の場合、edxの内容が2 n−1となり、nVarOneが正の場合、edxが0となり、最後にsar eax,3が2 nで除算されることに相当する.
2.除数が負の2のべき乗
直接例をあげます.

//.c
printf("nVarOne/-8=%d",nVarOne/-8);

コンパイル後の逆アセンブリ:

;.asm
 mov    eax, [esp+4]
 cdq
 and    edx,7
 add    eax,edx
 sar    eax,3
 neg    eax
...

最後の文を除いては上記と同じです.neg eaxは計算結果に負を取ることに相当します.
次に難点3と4について議論する
3.除数2以外のべき乗
次に、Cコードをアセンブリによって逆プッシュする例を示す.
シナリオ1(MagicNumber⩽0 x 7 FFFFFFF)
入手しやすい公式
xo⇔x∗2no∗12n
令
c=2 noであり,この値をMagic Numberと呼ぶ.そしてある
xo⇔x∗2no∗12n⇔x∗c2n

_main proc near
arg_0= dword ptr 4
    mov     ecx,[esp+arg_0]
    mov     eax,38E38E39h
    imul    ecx
    sar     edx,1
    mov     eax,edx
    shr     eax,1Fh
    add     edx,eax
    push    edx
    push    offset Format   ;"%d
    call    _printf
    add     esp,8
    retn
_main   endp

ここで,sar edx,1算術右シフト1ビット,shr eax,1Fh論理右シフト31ビットである.まず、ecx取得パラメータ、eax取得魔数、(edx,eax)=eax*ecx、積低4 Bのeaxコンテンツは捨てられ、積高4 Bのedxコンテンツのみを使用することで、積右シフト32ビットに相当し、sar edx,1右シフトの1ビットを加えて、共に右シフト33ビット、すなわちn=33、mov eax,edxとshr eax,1Fhを加算して積結果シンボルビットを取得し、積はタイミングeax格納00000000 h、積算ビットが負の場合は00000001 hを格納する.最後に、add edx,eaxの理由は、x<0であり、[xo]が整数でない場合、
[xo]=⌈x∗c2n⌉=⌊x∗c2n⌋+1
(ここではx<0であればコンパイラが確認できると思います
x∗c 2 nここでは必ず整数ではありません)
⑪o=2 nc=23338 E 38 E 39 h=8.99999……≒9,Cコードを導出し、

printf("%d",argc/9);

まとめ:

;x*(2^n/o)
 mov    eax,MagicNumber
 imul   ...
;/2^n
 sar    edx, ...
 mov    reg,edx
 shr    reg,1Fh
;    
 add    edx,reg

以上の命令シーケンスに遭遇すると,基本的に除算最適化後のコードであると判定できる.MagicNumber<=7 fffffffhであり、コンパイラはimulとsarの間に調整指令を発生していないため、除数を正数と認定する.統計的に右シフトの総回数は式中のn値を決定し,式o=2 nc(マジック数)を用いて除数oの近似値を得た.除算原型を復元できます.
シナリオ2(MagicNumber⩽0 x 7 FFFFFFF)
入手しやすい公式
xo⇔x∗232+232+no−232232+n
この式では、魔数
c=232+no−232

_main proc near
arg_0= dword ptr 4
 mov     ecx,[esp+arg_0]
 mov     eax,24924925h
 mul    ecx
 sub     ecx,edx
 shr     ecx,1
 add     ecx,edx
 shr     ecx,2
 push   ecx
 push   offset  Format ;"nVarTwo/7=%d\r
"
 call   _printf
 add     esp,8
 xor     eax,eax
 retn
_main endp

sub ecx,edx,shr ecx,1,add ecx,edx,shr ecx,2の4文は1つの計算式で表すことができる.
x−x∗c2322+x∗c23222
簡略化:
x∗232+c235
⑪232+n=235⇒n=3,o=232+n 232+c=235232+24925 h=6.99999……≒7,Cコードを出す:

printf("nVarTwo/7="%d\r
",argc/7);

まとめ:

 mov    eax,MagicNumber
 mul    reg
 sub    reg,edx
 shr    reg,1
 add    reg,edx
 (shr   reg,A)

以上の命令シーケンスに遭遇した場合,基本的に除算最適化後のコードであると判定できる.右シフト総回数を統計して式中のn値を決定し、式o=232+n 232+c(魔数)を用いて除数oを解くと、除法プロトタイプを復元することができる.
シナリオ3(MagicNumber≧0 x 8000000)
コンパイラはMagicNumberを計算する際に符号なしとして処理し,imul命令は符号付きとして処理する.したがって、マジック数≧0 x 8000000の場合、実際に乗算に参加するのは負の数であり、マジック数は数学式の「大きな定数」の意味と一致しない.
y真<0の場合、符号化計算式により、y補=232−|y真|=232+y真∈y真=y補−232‰x
入手しやすい公式
xo⇒x∗2 no∗12 n⇒(x∗(2 no−232)+x∗232)∗12 nすなわちxo⇒x∗y補(y無)∗12 n⇒(x∗y真+x∗232)∗12 n

_main proc near
arg_0= dword ptr 4
    mov     esi,[esp+arg_0]
    mov     eax,92492493h
    imul     esi
    add     edx,esi
    sar     edx,2
    ;...    

上記のコードを数式に変換します.
(esi∗eax+232∗esi)∗1234‰cは、コンパイラ求魔数演算が式c=2 no符号なしで演算されたものである.⑪式o=2 nc=234992492493 h=6.99999…≒7
逆押し出しCコード:

printf("%d",argc/7);

まとめ:

 mov    eax,MagicNumber;MagicNumber>7fffffffh
 imul   reg
 add    edx,reg
 sar    edx,...
 mov    reg,edx
 shr    reg,1Fh
 add    edx,reg

以上の命令シーケンスに遭遇した場合,基本的に除算最適化後のコードであると判定できる.MagicNumber≧8000000 hの場合、コンパイラはimulとsarの間に調整用のadd命令を生成するので、除数は正と判断できます.*右シフトの合計回数を統計して式中のn値を決定し、式o=2 nc(魔数)を用いて解除数oを求めると、除法原型が復元される.
4.除数が負の2以外のべき乗
入手可能な数式:
xo=x∗c∗12 n(c<0)c=−2 n|o|=2 n|o|補完=232−2 n|o|
シナリオ1(MagicNumber≧0 x 8000000)

_main proc near
arg_0= dword ptr 4
    mov      ecx,[esp+arg_0]
    mov      eax,99999999h
    imul     ecx
    sar      edx,1
    mov      eax,edx
    shr      eax,1Fh
    add      edx,eax
    push     edx
    push     offset Format ;"%d"
    call     _printf
    add      esp,8
    xor      eax,eax
    retn
_main endp

コード表現:
edx=ecx∗eax233|o|=2n232−c=233232−99999999h=4.999999……≈5
そこで、Cコードを逆発売しました.

printf("%d",argc/-5);

まとめ:

 mov    eax,MagicNumber(>=0x7fffffff)
 imul   reg
 sar    edx,...
 mov    reg,edx
 shr    reg,1Fh
 add    edx,reg

以上の命令シーケンスに遭遇すると,基本的に除算最適化後のコードであると判定できる.MagicNumber≧8000,000,000 h、コンパイラはimulとsarの間に調整命令を発生していないため、除数が負であると認定できます.*合計右シフト数を統計して式中のn値を決定し、式|o|=2 n 232−c(マジック数)を用いて解除数|o|を求めると、除法プロトタイプが復元される.
シナリオ2(MagicNumber⩽0 x 7 FFFFFFF)MagicNumber<=7 FFFFFFFFhの場合、除数も負になる可能性がある.(なぜこのようなシナリオがあるのか?数学式ではc=2 noで表される範囲をより大きくすることができる)x∗c 2 nではc=2 no(o<0)でより小さな負数を表すために、コンパイラは3中シナリオ3のような方法で、
p=−oとし,(p>0)xo=−xp⇒−−(x∗2 np∗12 n)⇒−((x∗(2 np−232)+ x∗232)⇒( x∗(−(2 np−232))−x∗232)⇒( x∗(−(2 np−232))−x∗232))⇒( x∗(232−2−2−2 n|o|)−x∗232)−n∗12n⇒(x∗(232−−2−−2 n|o|)−x∗232)−n n n n n∗12n⇒(n n n)⇒(n⇒x∗c−2322 n(コード変換対応式)−c=2 np−232<0(3中シナリオ3のy真)c=−(2 np−232)=232−2 np=232−2 n｜o|>0

_main proc near
arg_0= dword ptr 4
    mov      ecx,[esp+arg_0]
    mov      eax,6DB6DB6Dh
    imul     ecx
    sub      edx,ecx
    sar      edx,2
    mov      eax,edx
    shr      eax,1Fh
    add      edx,eax
    push     edx
    push     offset Format ;"%d"
    call     _printf
    add      esp,8
    retn
_main endp

上のコードは数式に変換されます.
edx=edx∗eax232−ecx22=ecx∗eax−232∗ecx234=ecx∗eax−232234ecxo=ecx∗eax−232234|o|=2n232−c=234232−6DB6DB6Dh=6.999999……≈7
そこでCコードを反転:

printf("%d",argc/-7);

まとめ:

 mov    eax,MagicNumber(<=7fffffffh)
 imul   reg
 sub    edx,reg
 sar    edx,...
 mov    reg,edx
 shr    reg,1Fh
 add    edx,reg

以上の命令シーケンスに遭遇した場合,基本判定は除算最適化後のコードである.MagicNumber 7 fffffffh,imulとsarの間にsub命令があり積を調整するので,除数は負であると認定した.合計右シフト数を統計して式中のn値を決定し、式|o|=2 n 232−c(マジック数)を用いて解除数|o|を求めると、除法プロトタイプが復元される.
アセンブリコードから正負の除数を区別するにはどうすればいいですか?∙MagicNumberの最高位が1の場合(≧8000000 h)、正除数に対してMagicNumberは元のコード形式であり、コンパイラはimulとsarの間に調整作用のあるadd命令を生成する.ない場合は、MagicNumberが符号化されます.∙MagicNumberの最上位が0の場合(⩽7 FFFFFh)、負の除数の場合、コンパイラはimulとsarの間で調整作用のあるsub命令を生成します.これらは負の除数を区別する重要な根拠とすべきである.