程序分析期末考试

中山大学软件工程学院 thinkerhui 出题

选择题（单选）

1. 理想的静态程序分析具有什么特性？
   A. Fast B. Robust C.Sound&Complete D.以上都是
2. 要使静态程序分析能得到Sound结果，应该采用：
   A. Underapproximate B. Overapproximate C. Aboveapproximate D.Upapproximate
3. 静态程序分析的处理对象（输入）一般是什么？
   A. IR（3AC) B. Tokens C. AST D. CFG
4. 控制流图(CFG)的节点是什么？
   A.基本块 B.控制流 C.IR语句 D.数据块
5. 下面对活变量分析(Live Variables Analysis)的解释，最准确的是：
   A. 活变量分析判断在某个程序点p一个变量v的值能否在点p之后的某条CFG路径上被使用，如果有被使用，则v在p点是活的，否则v是死的。
   B. 活变量分析判断在某个程序点p一个变量v的值能否在点p之前的某条CFG路径上被使用，如果有被使用，则v在p点是活的，否则v是死的。
   C. 活变量分析判断一个变量v的值能否到达程序点p，如果能到达p点，则v在p点是活的，否则v是死的。
   D. 活变量分析判断在某个程序点p一个变量v的值能否在点p之后的所有CFG路径上是否全部都被使用，如果都被使用，则v在p点是活的，否则v是死的。
6. 下面哪个不是指针分析的关键因素？
   A. 堆抽象(Heap abstraction) B. 数据敏感(Data sensitivity) C. 分析范围(Analysis scope) D. 流敏感(Flow sensitivity)
7. 对于上下文敏感的堆分配(allocation-site)抽象，最常用的上下文信息是：
   A. 对象类型 B.调用位置 C.调用对象 D.调用类型
8. 对于机密性(Confidentiality)和完全性(Integrity)，下面说法错误的是：
   A. 高机密性(High secret)的秘密文件不允许被低机密性(High secret)的公众写入修改。
   B. 高机密性(High secret)的文件不允许被低机密性(High secret)的公众读取。
   C. 高完全性(High integrity)的可信文件不允许被低完全性(Low integrity)的不可信用户读取。
   D. 高完全性(High integrity)的可信文件不允许被低完全性(Low integrity)的不可信用户写入修改。

选择题（多选）

1. 对于一个compromise complete的静态程序分析，分析出的程序行为可能会是：
   A. False Positives B. True Positives C.True Negatives D.False Negatives
2. 下面的哪些静态分析是May Analysis的？
   A. 定义到达分析(Reaching Definition) B.活变量分析(Live Variables) C.可用表达式分析(Available Expression) D.常量传播分析 E.指针分析
3. 对于下面的程序，正确的Resolve有：
   <img src="https://sse-market-source-1320172928.cos.ap-guangzhou.myqcloud.com/blog/image-20240703220041260.png" alt="image-20240703220041260" style="zoom: 25%;" />
   A. Resolve(b.foo())={A.foo(),C.foo(),D.foo()} B. Resolve(A.foo())={A.foo()}
   C. Resolve(c.foo())={A.foo(),C.foo()} D. Resolve(C.foo())={C.foo()}
4. 指针流图(Pointer Flow Graph)的节点可以是：
   A. 一个变量(a variable) B.一个抽象对象(an abstract object) C.一个变量的域(a field of a variable) D.一个抽象对象的域(a field of an abstact object)

填空题

1. 指针分析的四个关键因素是：___,____,____和___
2. 指针分析的规则包括：____,Assign , ____, ____ 和 Call
3. Datalog语言的四个特性：___, 没有控制流，__,图灵不完备

简答题

1. 静态程序分析与动态测试的区别是什么？
2. 为什么静态程序分析通常要求Soundness？
3. 运用IFDS来解决静态程序分析问题的基本思想是什么？解决的步骤是什么？
4. 调用位置上下文敏感的静态程序分析为什么在实践中要进行K阶约束(k-Limiting)？
5. Soundiness和Soundness的区别是什么？为什么要提出Soundiness的概念？
6. 为什么Java的relection和native code特性会很难进行静态分析？

程序分析题

1. 请对下面的程序进行(上下文不敏感)过程间常量传播分析,要写出构建的ICFG和常量传播分析的最终结果(不用写算法推理过程):

static void main(){
    int z = 3;
    int x = One(z);
    z = x;
    int a = x+2;
    int b = z;
    if (a<x){
        x=One(z);
    }
}
static int One(int x){
    int y = x + 1;
    return y;
}

调用图构建算法：
<img src="https://sse-market-source-1320172928.cos.ap-guangzhou.myqcloud.com/blog/image-20240703230710727.png" alt="image-20240703230710727" style="zoom: 50%;" />

常量分析算法：
<img src="https://sse-market-source-1320172928.cos.ap-guangzhou.myqcloud.com/blog/image-20240703231010445.png" alt="image-20240703231010445" style="zoom:50%;" />

2. 在下面CFG的基础上进行活变量分析，写出分析的最终结果(对算法过程不作要求)
   <img src="https://sse-market-source-1320172928.cos.ap-guangzhou.myqcloud.com/blog/image-20240703231736026.png" alt="image-20240703231736026" style="zoom:25%;" /><img src="https://sse-market-source-1320172928.cos.ap-guangzhou.myqcloud.com/blog/image-20240703231414735.png" alt="image-20240703231414735" style="zoom:50%;" />

参考答案

选择题

单选题 1~8 CBAAABBC

多选题 1. ABCD 2. ABDE 3. ABD 4. AD

简答题

1. 动态测试是指在运行时状态对程序输入数据并检验运行结果来验证程序的软件测试技术。而静态程序分析是指在程序不运行的情况下，对程序的执行进行分析的技术。二者的主要区别在于是否运行程序。
2. 静态分析技术通常要求Soundess可以从两个方面考虑：第一，Soundness对于某些静态程序分析的应用至关重要，如程序验证和代码优化。Soundness可以保证这些程序分析的应用不会出错，提高安全性。第二，对于Soundness不是必须的那些静态程序分析具体应用，比如bug检测，sound的程序分析往往可以得出更符合实际需求的结果。
3. 运用IFDS来解决静态程序分析问题的基本思想是利用上下文无关文法可达性的原理(CFL-Reachability)，将程序分析转化为图可达问题来计算程序所有可能的执行情况，再运用MRP(Meet over all path)来计算出程序分析问题的解。这个过程可以分为三个步骤来完成：1.将静态程序分析问题转化为超图（supergraph）G*，并定义流函数（flow function）。2.通过把流函数转化为(二元)表示形式，将超图转化为explode 超图G#。3.在G#上应用Tabulation算法来找到图可达问题的MRP解，从而解决静态程序分析问题。
4. 调用位置上下文敏感的分析之所以需要进行k阶约束，是出于两点考虑：1.为了确保程序分析可以运行结束。2.避免上下文信息过多（因为现实程序的调用链可能很长）。
5. soundness指静态程序分析可以计算出程序所有可能的动态执行行为而不会遗漏。Soundiness则是指静态程序分析可以计算出程序除了部分高级语言特性之外的所有可能的动态执行行为，对于这些高级语言特性的程序片段作出合理性的分析即可，而不要求分析是完全的。由于在现实情况中，我们目前还没有有效的自动化方法来确保对高级语言特性的程序片段作出sound的分析技术，也就是要求soundness是不可行的，所以实际的静态程序分析需要采用soundiness标准。
6. java的relection技术会在运行时状态产生新的类、对象及方法，导致无法在不运行程序的时候进行有效准确的分析。java的native code特性意味着在java程序中会调用底层平台的C/C++方法，这些JNI方法有两百多个，可以进行各种各样的操作，但是目前并没有有效的程序分析手段，需要花费大量的人力才能完成分析。