1. 區(qū)間圖：用于局部寄存器分配，基本塊內(nèi)的每個(gè)活躍范圍看作一個(gè)區(qū)間（最早定義位置+最新使用位置），所有活躍范圍構(gòu)成區(qū)間圖。區(qū)間圖是一種不精確的沖突圖（因?yàn)楦吖懒嘶钴S范圍的范圍而導(dǎo)致偽沖突，比如認(rèn)為一個(gè)復(fù)制操作連接的或兩個(gè)源相同目標(biāo)不同的復(fù)制操作產(chǎn)生重疊的兩個(gè)活躍范圍沖突，但實(shí)際沒(méi)有沖突），優(yōu)勢(shì)在于著色是P（復(fù)雜度O(|V|)或O(|E|)）而非NP問(wèn)題。llvm早期的線性掃描分配器是基于區(qū)間圖在全局的擴(kuò)展，比較適用于JIT編譯（減少編譯時(shí)間）
2. 一般圖：用于全局寄存器分配，是一種精確的沖突圖（由一組定義與一組使用構(gòu)成的網(wǎng)絡(luò)）。優(yōu)勢(shì)在于努力最小化溢出活躍范圍而生成高效執(zhí)行的代碼，但會(huì)犧牲編譯時(shí)間。llvm的greedy寄存器分配是基于一般圖的代表。編譯器使用的沖突圖可能會(huì)將機(jī)器約束條件比如多寄存器值/調(diào)用約定編碼進(jìn)去而存在重復(fù)邊，導(dǎo)致不滿足圖論中的簡(jiǎn)單圖定義，故這里采用一般圖
3. 弦圖：定義詳見
https://oi-wiki.org/graph/chord。基于靜態(tài)單賦值形式名建立的沖突圖是弦圖。優(yōu)勢(shì)在于可以做到最佳著色（復(fù)雜度O(|V|+|E|)）而非啟發(fā)式（基于一般圖的全局寄存器分配使用啟發(fā)式），利于減少寄存器壓力。劣勢(shì)在于必須將指派寄存器后的仍然為靜態(tài)單賦值代碼轉(zhuǎn)換為機(jī)器碼，而這種轉(zhuǎn)換可能增加寄存器壓力，以及插入一些可能非必要的復(fù)制操作，若復(fù)制操作實(shí)現(xiàn)的數(shù)據(jù)流與ssa phi函數(shù)對(duì)應(yīng)，則分配器無(wú)法合并這種復(fù)制，這將破壞弦圖的性質(zhì)
4. 沖突圖拆分：查找其中的團(tuán)分割即連通子圖，移除它劃分得到不相交的一些子圖，這樣一來(lái)，各子圖可獨(dú)立著色（有點(diǎn)類似活躍范圍拆分）而利于減少寄存器壓力，另外實(shí)現(xiàn)上還能節(jié)省下三角布爾矩陣（用于快速判斷兩結(jié)點(diǎn)是否沖突）的規(guī)模
#############################
寄存器分配與圖論的染色理論相關(guān)。其它的比如常量傳播與格代數(shù)及不動(dòng)點(diǎn)相關(guān)，循環(huán)優(yōu)化與多面體、矩陣相關(guān)。這三方面是我目前看到的編譯器所用數(shù)學(xué)理論
有單向、雙向、三向3種認(rèn)證方式，前兩者必須檢查時(shí)間戳以防重放攻擊，單向因?yàn)橹挥幸粋€(gè)消息傳遞，如果僅靠一次性隨機(jī)數(shù)是無(wú)法判斷消息是否重放。雙向有兩個(gè)消息傳遞，一來(lái)一回，僅靠一次性隨機(jī)數(shù)只能檢測(cè)到發(fā)響應(yīng)那方的重放。最后者則不必，可僅通過(guò)一次性隨機(jī)數(shù)檢測(cè)自己是否遭遇重放攻擊，因?yàn)榻邮盏诙€(gè)消息的那方，通過(guò)判斷第二個(gè)消息中隨機(jī)數(shù)是否等于自己先前已發(fā)送第一個(gè)消息中的那個(gè)，若不等于則為重放，若等于則發(fā)第三個(gè)確認(rèn)消息給對(duì)方，對(duì)方收到并判斷確認(rèn)消息中的隨機(jī)數(shù)是否等于先前它已發(fā)送第二個(gè)消息中的隨機(jī)數(shù)，若等于則說(shuō)明第它收到的第一個(gè)消息的確是另一方發(fā)送的即非重放，否則為重放。因此三向認(rèn)證可不必同步雙方時(shí)鐘。但正因?yàn)椴粡?qiáng)制檢查時(shí)間戳而可能導(dǎo)致
中間人攻擊：假設(shè)通信雙方為A、B，中間人為C，攻擊步驟如下
1. C與B認(rèn)證時(shí)，發(fā)送先前已截獲的A到B請(qǐng)求消息給B
2. 截獲并存儲(chǔ)B到A的響應(yīng)消息x，但不轉(zhuǎn)發(fā)，開始與A認(rèn)證
3. 收到A的請(qǐng)求消息后，解密x取出其中的隨機(jī)數(shù)Rb作為響應(yīng)給A消息中的隨機(jī)數(shù)，用自己私鑰簽署整個(gè)消息后發(fā)給A
4. 收到并轉(zhuǎn)發(fā)A的確認(rèn)消息給B
以上完成后，C就能冒充A與B通信了。一種簡(jiǎn)單的改進(jìn)方法是先用對(duì)方的公鑰加密消息中的隨機(jī)數(shù)，再用自己的私鑰簽署整個(gè)消息。關(guān)于網(wǎng)絡(luò)協(xié)議的安全性分析，主流方法是形式化分析，可以借助相關(guān)工具來(lái)驗(yàn)證找出漏洞
1.
對(duì)于RSA，給定大整數(shù)n分解的一對(duì)素因子p和q，p或q是否素?cái)?shù)決定不了安全性，但決定算法的正確性，也就是說(shuō)p或q不能為合數(shù)，而安全性取決于n的位數(shù)及p、q的距離，n越大則難于素因子分解（因?yàn)樗財(cái)?shù)測(cè)試是一個(gè)P問(wèn)題，而因子分解是一個(gè)NP問(wèn)題，其耗時(shí)是關(guān)于n的指數(shù)），|p - q|要大是為抵抗一種
特殊因子分解攻擊，論證如下：由(p+q)
2/4 - n = (p+q)
2/4 - pq = (p-q)
2/4，若|p - q|小，則(p-q)
2/4也小，因此(p+q)
2/4稍大于n，(p+q)/2稍大于n
1/2即根號(hào)n。可得n的如下分解法：a) 先順序檢查大于n
1/2的每一整數(shù)x，直至找到一個(gè)x使得x
2 - n是某一整數(shù)y的平方；b) 再由x
2 - n = y
2 得 n = (x+y)(x-y)。另外，p - 1和q - 1都應(yīng)有大素因子（所有因子皆是大素?cái)?shù)），以抵抗可能的
重復(fù)加密攻擊（重復(fù)加密較少步后可恢復(fù)出明文）
2.
對(duì)于DH密鑰交換，通常選擇階為素?cái)?shù)的有限循環(huán)(子)群，這時(shí)素?cái)?shù)決定了安全性。因素?cái)?shù)不能再因子分解，故避免了針對(duì)階為合數(shù)的質(zhì)因子分解且利用中國(guó)剩余定理求離散對(duì)數(shù)的(已知最好)攻擊。具體講就是為了防
index-calculus方法求解離散對(duì)數(shù)，底層循環(huán)群G的素?cái)?shù)模p要足夠大，長(zhǎng)度1024位可實(shí)現(xiàn)80位安全等級(jí)，長(zhǎng)度3072位可實(shí)現(xiàn)128位安全等級(jí)；另為了防
Pohlig-Hellman攻擊，G的階p-1必須不能因式分解為全部都是小整數(shù)的素?cái)?shù)因子，且為了p-1的每個(gè)因子構(gòu)成的子群防
baby-step giant-step或
Pollards's rho攻擊，要求對(duì)80位安全等級(jí)而言，p-1的最小素因子必須至少為160位，而對(duì)128位安全等級(jí)，其至少為256位
3.
對(duì)于Hash函數(shù)，安全性要求有三點(diǎn)：第一是單向性，由于壓縮函數(shù)理論上存在碰撞，因此單向性是指計(jì)算不可行，為什么要單向性？因?yàn)槿舨粏蜗颍瑒t可從結(jié)果比如簽名逆出原文消息；第二是抗弱沖突性即
第1類生日攻擊，計(jì)算不可行；第三是抗強(qiáng)沖突性即
第2類生日攻擊，計(jì)算不可行。這三點(diǎn)要求，取決于壓縮函數(shù)是否能抗差分、線性等密碼分析
4. 周知
Shamir門限方案基于多項(xiàng)式的拉格朗日插值公式，普遍的設(shè)計(jì)采用GF(q)域上的多項(xiàng)式，秘密s為f(0)，q是一個(gè)大于n的大素?cái)?shù)（n是s被分成的部分?jǐn)?shù)）。正常來(lái)講，參與者個(gè)數(shù)必須至少是設(shè)計(jì)時(shí)的k，才能恢復(fù)出正確的s。如果個(gè)數(shù)少于k比如k-1，則只能猜測(cè)s0=f(0)以構(gòu)建第k個(gè)方程，那么恢復(fù)得到的多項(xiàng)式g(x)等同設(shè)計(jì)時(shí)的多項(xiàng)式f(x)的概率是1/q。因?yàn)間(x)的項(xiàng)系數(shù)可以看作關(guān)于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q為素?cái)?shù)，故依模剩余系遍歷定理，當(dāng)s0取GF(q)一值時(shí)，則h(s0)唯一對(duì)應(yīng)另一值。所以h(s0)等于f(0)的概率為1/q。由此可見，當(dāng)q取80位以上，敵手攻擊概率不大于1/2
80，這已經(jīng)很低了。這種門限方案如同RSA加密，再次佐證了素?cái)?shù)越大安全性越高
5.
PGP是密碼學(xué)經(jīng)典應(yīng)用，體現(xiàn)在首先支持保密與認(rèn)證業(yè)務(wù)的正交，即獨(dú)立或組合，且組合時(shí)按認(rèn)證、壓縮、加密的順序，這個(gè)順序是經(jīng)考究有優(yōu)勢(shì)的；其次會(huì)話密鑰是一次性的，由安全偽隨機(jī)數(shù)生成器生成，且按公鑰加密；最后使用自研的密鑰環(huán)與信任網(wǎng)解決公鑰管理問(wèn)題。理論本質(zhì)上，PGP提供的是一種保密認(rèn)證業(yè)務(wù)的通用框架，因?yàn)榫唧w的對(duì)稱加密算法、隨機(jī)數(shù)生成、公鑰算法，都可依需要靈活選配擴(kuò)展。PGP有兩個(gè)問(wèn)題跟組合與概率相關(guān)，一個(gè)是算密鑰環(huán)N個(gè)公鑰中，密鑰ID(64位)至少有兩個(gè)重復(fù)的概率？設(shè)所求概率為p，先算任意兩個(gè)不重復(fù)的概率q，令m=2
64，則q=m!/((m-N)!*m
N)，則p=1-q，不難看出，N越小則q越大則p越小，因?qū)嶋H應(yīng)用N<<m，故p非常小可忽略，即PGP取公鑰中最低64有效位作密鑰ID，是可行的。另一個(gè)是簽名摘要暴露了前16位明文，對(duì)哈希函數(shù)安全的影響有多大？這問(wèn)題意思應(yīng)該是敵手拿到消息后但沒(méi)發(fā)送方的私鑰作簽名，只能窮舉變換原消息并求哈希值，使之與消息摘要剩余位組相等。這本質(zhì)是求
兩類生日攻擊碰撞概率大于0.5時(shí)所需的輸入量。在僅認(rèn)證模式中，抗弱碰撞計(jì)算量降低為原來(lái)的1/2
16，抗強(qiáng)碰撞計(jì)算量至少降低為原來(lái)的1/2
8。另外，考慮到這16位明文可能的特殊性，有沒(méi)更快的代數(shù)攻擊，需進(jìn)一步研究
周知編譯原理龍書闡述的基本塊指令調(diào)度算法，它所使用的空的資源預(yù)約表RTD與每個(gè)指令的資源預(yù)約表RT，可以看作二維矩陣，行表示時(shí)鐘周期、列表示cpu資源，其定位的元素值1表示占用/預(yù)約，0表示空閑/非預(yù)約。前者是隨周期遞增而動(dòng)態(tài)擴(kuò)大的矩陣，后者是固定尺寸(維數(shù))的矩陣（指令花費(fèi)周期與每周期預(yù)約資源皆已知）。在調(diào)度時(shí)，按帶優(yōu)先級(jí)比如關(guān)鍵路徑的拓?fù)渑判蚧緣K內(nèi)的指令，順序選取一條指令I(lǐng)nst，計(jì)算每前驅(qū)發(fā)射周期加延遲的結(jié)果tmp，取所有tmp的最大值tmax作為Inst的發(fā)射周期，再判斷處理器資源是否可用，即RTD和RT作
與運(yùn)算，得到一個(gè)新矩陣RTN，若RTN為
全零矩陣則tmax為Inst的最終發(fā)射周期，否則遞增tmax再做矩陣與運(yùn)算，直至得到全零矩陣。最后更新RTD，即RTD與RT作
或運(yùn)算結(jié)果存于RTD。重復(fù)上述過(guò)程直到基本塊末尾。
綜上不難看出，如果一個(gè)基本塊很大比如有1000條指令，平均每指令花2個(gè)周期，則RTD需要2000個(gè)條目，若一條目即矩陣每行占用32字節(jié)（256種資源數(shù)），則總量約64k。當(dāng)然這對(duì)于現(xiàn)代內(nèi)存體量來(lái)說(shuō)不算什么，但可以有更好的節(jié)省內(nèi)存的做法：RTD尺寸其實(shí)可以相對(duì)固定，其上限為基本塊中耗費(fèi)周期最多指令的周期的一個(gè)大于1常數(shù)因子倍（為兼顧指令并行性），這樣一來(lái)就要增加當(dāng)指令完成時(shí)（當(dāng)前指令發(fā)射周期大于前一條的終止周期時(shí)復(fù)位前一條指令的RTD）從發(fā)射周期處復(fù)位RTD即作一個(gè)矩陣反運(yùn)算的操作，其它步驟對(duì)應(yīng)的矩陣與、矩陣或運(yùn)算的操作保留不變。另由于RTD固定了尺寸，因此發(fā)射周期遞增后要取模
【備注】以上是我針對(duì)簡(jiǎn)單機(jī)器模型（每種資源數(shù)量?jī)H一個(gè)，比如整數(shù)運(yùn)算單元1個(gè)，內(nèi)存訪問(wèn)單元1個(gè)，浮點(diǎn)運(yùn)算單元1個(gè)）用布爾矩陣作的優(yōu)化。如果是復(fù)雜的超標(biāo)量機(jī)器即每種資源數(shù)有多個(gè)，那么只需修改如下：布爾矩陣換成整數(shù)矩陣；新增一個(gè)機(jī)器資源可用總數(shù)整數(shù)矩陣RDA（單列資源數(shù)同值），布爾矩陣與運(yùn)算換成加法并與RDA比較，若大于RDA則遞增tmax；布爾矩陣或運(yùn)算換成加法；布爾矩陣反運(yùn)算換成減法，RTD減RT存于RTD
曾因朋友問(wèn)到監(jiān)控，致使我探究了kretprobe的實(shí)現(xiàn)，想到編譯中的尾調(diào)用優(yōu)化，作個(gè)小結(jié)
?1. kretprobe_trampoline_holder該跳轉(zhuǎn)函數(shù)無(wú)參是必須的或說(shuō)最好的通用設(shè)計(jì)，因?yàn)樘鎿Q返回地址是非正常程序流程，即被探測(cè)函數(shù)的調(diào)用者無(wú)感知，不存在為跳轉(zhuǎn)函數(shù)準(zhǔn)備入?yún)ⅰＨ粢O(shè)計(jì)傳參且只讀，則不會(huì)破壞被探測(cè)函數(shù)調(diào)用者的上下文，但跳轉(zhuǎn)函數(shù)內(nèi)部流程怎么用參數(shù)是個(gè)問(wèn)題，這需要一種約定
?2. 跳轉(zhuǎn)函數(shù)為調(diào)用trampoline_handler準(zhǔn)備入?yún)ⅲ丛跅Ｉ蠘?gòu)造一個(gè)（不完整的）pt_regs，再把它地址即棧頂賦給rdi，rdi是x86_64上傳入第一參數(shù)使用的寄存器，同時(shí)預(yù)留一個(gè)棧單元存放原返回地址（為什么要預(yù)留？因?yàn)楸惶綔y(cè)函數(shù)返回時(shí)，其調(diào)用者存放返回地址的棧空間被釋放了，所以得在跳轉(zhuǎn)函數(shù)內(nèi)造一個(gè)）。由于trampoline_handler內(nèi)調(diào)到用戶自定義handler而傳入pt_regs，因此自定義handler內(nèi)要注意最好別改動(dòng)pt_regs，否則會(huì)破壞被探測(cè)函數(shù)調(diào)用者的上下文
有理數(shù)域的本原多項(xiàng)式與有限域的本原多項(xiàng)式定義不同，前者不要求不可約（由高斯引理知兩個(gè)本原多項(xiàng)式的乘積還是本原），后者則必須不可約（確保生成的有限域其每個(gè)元素有逆元）。aes基于有限域F{0,1}設(shè)計(jì)，故使用的模8次多項(xiàng)式不可約
P(x)=x^8+x^4+x^3+x+1，但不是本原多項(xiàng)式，因?yàn)樗碾A是51而非255。有限域次數(shù)為8的本原多項(xiàng)式有16個(gè)、不可約多項(xiàng)式有30個(gè)（由莫比烏斯反演推出），具體多項(xiàng)式影響s盒與列混合操作的實(shí)現(xiàn)。不可約加之0的逆元規(guī)定為0，保證正確加解密。若0的逆元規(guī)定為非0比如x，則導(dǎo)致x有兩個(gè)逆元，便違反了逆元唯一性，除非s盒不用有限域設(shè)計(jì)。逆元等于其自身的非0元素只有1，原因可類比模素?cái)?shù)二次剩余的求解
1. 若DFA D是用子集構(gòu)造法從NFA N構(gòu)造出來(lái)的，則L(D)=L(N)
2. 一個(gè)語(yǔ)言L被某個(gè)DFA接受，當(dāng)且僅當(dāng)被某個(gè)NFA接受
3. 一個(gè)語(yǔ)言L被某個(gè)£-NFA接受，當(dāng)且僅當(dāng)被某個(gè)DFA接受
4. 若對(duì)于某個(gè)DFA A，L=L(A)，則存在一個(gè)正則表達(dá)式R使得L=L(R)
5. 每一個(gè)用正則表達(dá)式定義的語(yǔ)言也可用有窮自動(dòng)機(jī)定義
6. 若通過(guò)填表算法不能區(qū)分兩個(gè)狀態(tài)，則它們是等價(jià)的
7. DFA的狀態(tài)等價(jià)性是傳遞的
8. 若對(duì)于DFA每個(gè)狀態(tài)q及與q等價(jià)的所有狀態(tài)組成塊，則不同的狀態(tài)塊形成狀態(tài)集合的劃分。也就是說(shuō)，每個(gè)狀態(tài)恰好屬于一個(gè)塊，同一塊中的所有成員都是等價(jià)的，從不同塊中選擇的狀態(tài)對(duì)都不是等價(jià)的
9. 根據(jù)等價(jià)狀態(tài)劃分算法最小化DFA D得到的DFA M是唯一的。也就是說(shuō)，不存在其它等價(jià)于D的DFA N，其狀態(tài)數(shù)比M少
----------------------------------------------------------------------------------------
10. 對(duì)于正則表達(dá)式，空集是并運(yùn)算的單位元、連接運(yùn)算的零元，空串是連接運(yùn)算的單位元
11. 若L和M都是正則語(yǔ)言，則L和M的并、交、差也是
12. 若L是字母表T上的正則語(yǔ)言，則~L=T*—L也是
13. 若L是正則語(yǔ)言，則L的反轉(zhuǎn)也是
14. 若L是字母表T上的正則語(yǔ)言，h是T上的一個(gè)同態(tài)，則h(L)也是正則的
15. 若h是字母表A到字母表T的同態(tài)，且L是T上的正則語(yǔ)言，則逆同態(tài)h^-1(L)也是正則的
1. 空性：對(duì)于R，若給定形式是自動(dòng)機(jī)比如£-NFA，則等價(jià)于判定能否從初始狀態(tài)到達(dá)接受狀態(tài)，這需計(jì)算可達(dá)狀態(tài)集合，若任一接受狀態(tài)在里面，則為非空，否則為空。耗時(shí)不超過(guò)O(n^2)，n為自動(dòng)機(jī)的狀態(tài)數(shù)。若給定形式是正則表達(dá)式，則可先轉(zhuǎn)為£-NFA，再計(jì)算可達(dá)狀態(tài)集合，如此增多轉(zhuǎn)化時(shí)間O(s)，s為正則表達(dá)式的長(zhǎng)度。也可不轉(zhuǎn)為自動(dòng)機(jī)，直接根據(jù)基礎(chǔ)歸納規(guī)則用遞推法判定，耗時(shí)為O(s)。 對(duì)于CFL，等價(jià)于判定開始符號(hào)是否為產(chǎn)生的，若是則非空，否則為空。如直接用產(chǎn)生變?cè)幕A(chǔ)歸納法計(jì)算，那耗時(shí)O(n^2)，n為文法G的規(guī)模，接近變?cè)膫€(gè)數(shù)。一個(gè)改進(jìn)的算法實(shí)現(xiàn)，預(yù)先建立以變?cè)獮樗饕臄?shù)組、每個(gè)變?cè)逆溄樱óa(chǎn)生式內(nèi)鏈接、產(chǎn)生式間鏈接），則耗時(shí)O(n)
2. 成員性：設(shè)串w的長(zhǎng)度為n。對(duì)于R，等價(jià)于判定自動(dòng)機(jī)能否接受w，若給定形式是DFA，則耗時(shí)O(n)。若給定形式是NFA，則耗時(shí)O(n*s^2)，s為狀態(tài)數(shù)，如NFA有£轉(zhuǎn)移，那需先計(jì)算它的閉包，耗時(shí)增多O(s^2)，可見總耗時(shí)還是O(n*s^2)。若給定形式是正則表達(dá)式，則先轉(zhuǎn)為NFA，耗時(shí)增多O(r)，r為表達(dá)式的長(zhǎng)度。 對(duì)于CFL，等價(jià)于判定從文法G的開始符號(hào)S能否推導(dǎo)出w，一般用CYK算法構(gòu)造產(chǎn)生式三角表，再查看S是否屬于表的頂點(diǎn)集合，若屬于則能推導(dǎo)出w，否則不能，耗時(shí)為O(n^3)