Page 12 - 《软件学报》2021年第6期

1586 Journal of Software 软件学报 Vol.32, No.6, June 2021

FCSG 是一个四元组结构 G=(F,R,S,f 0 ),其中,
• F 是一个符号集合;
+
• R 是定义在 F 上的二元关系:R={〈f i ,f j 〉 k |f i ∈F,f j ∈F,k∈Z },下标 k 表示对集合中相同的 f i 和 f j 构成的关系
的区分.且∀k≥2,若〈f i ,f j 〉 k ∈R,则〈f i ,f j 〉 k−1 ∈R.当 k=1 时,简记为 r=〈f i ,f j 〉;
• S 是集合 R 到正整数集 Z+的映射,满足:
¾ ∀〈f i ,f j 〉 k ∈R,有 S(〈f i ,f j 〉 k )=s,s≥k;
¾ ∀〈f i ,f j 〉 k ∈R,∀〈f i ,f j′ 〉 k′ ∈R,若〈f i ,f j′ 〉 k′ ≠〈f i ,f j 〉 k ,则 S(〈f i ,f j′ 〉 k′ )≠S(〈f i ,f j 〉 k );
¾ ∀S(〈f i ,f j 〉 k )=s,若 s>1,则∃〈f i ,f j′ 〉 k′ ∈R,S(〈f i ,f j′ 〉 k′ )=s−1;
• f 0 ∈F,且Œf∈F,〈f,f 0 〉∈R.
符号集合 F 对应一个 C 程序 P 中的所有函数集合.考虑 C 语言中不支持函数重载,故可用函数名表示程序
中的函数.集合 R 用来刻画程序 P 中的函数调用关系,∀f i ∈F,f j ∈F,若程序 P 中的函数 f i 的定义中存在函数 f j 的调
用语句,且在函数中的调用是第 k 次出现,则有〈f i ,f j 〉 k ∈R;若该次调用是 f i 函数体中出现的第 s 个函数调用语句,
则有 S(〈f i ,f j 〉 k )=s.程序 P 的入口函数记为 f 0 ,显然,一个良好程序的入口函数不会在其他函数中被调用.在关系集
合 R 中,k 是对相同的函数调用关系的编号,用以区分这些相同函数调用.
在协议代码 FCSG 结构的基础上,定义获取函数调用静态执行序列(static execution of call sequence,简称
SECS)算法,将其命名为 FCSG-SECS 算法,算法描述如下:
算法 1. 函数调用静态执行序列获取算法 FCSG-SECS(G).
输入:G=(F,R,S,f 0 );
输出:函数调用静态执行序列 SECS.
1. SECS=[⋅];
2. If G.F=∅ then
3. Return [⋅];
4. EndIf
5. R 0 ={〈G.f 0 ,f′〉 k |〈G.f 0 ,f′〉 k ∈G.R};
6. 将 R 0 按照 G.S 的映射值升序排序;
7. Foreach 〈f 0 ,f′〉 k ∈R 0 do
8. SECS.append(〈f 0 ,f′〉 k );
9. G′=(F/f 0 ,R/〈f 0 ,f′〉 k ,S/(〈f 0 ,f′〉 k →s′),f′);
10. SECS.append(FCSG-SECS(G′));
11. EndFor
12. Return SECS
函数调用时序图中蕴含了静态模拟执行代码的函数调用顺序.从入口函数出发,对协议代码对应的 FCSG
按出边的标号属性顺序(升序),遍历所有函数调用关系,便可以得到程序代码的函数调用执行序列.我们用图 2
中的示例代码来具体说明.图 2 是一段示例代码和其对应的 FCSG 图.

void foo() { }
void bar() {
foo();
}
void main() {
bar();
foo();
bar();
}

Fig.2 Example for function calls and FCSG
图 2 函数调用及 FCSG 示例