Field-Sensitive Alias

Release:

6.1.2

Date:

Oct 28, 2026

Field-sensitive alias graphs for C programs: memory locations are distinguished by the struct field they occupy, so aliasing is tracked per field (the f_i family), as in “Taming Transitive Redundancy for Context-Free Language Reachability”.

Graph	Num Nodes	Num Edges	Reachable pairs	Size (MB)	Download
xz	2808	6604	205164	0.536	xz_field_sensitive_alias.tar.gz 📥
nab	3444	7982	262566	0.677	nab_field_sensitive_alias.tar.gz 📥
leela	8090	19888	3968276	9.92	leela_field_sensitive_alias.tar.gz 📥
povray	15137	38886	27219043	0.080	povray_field_sensitive_alias.tar.gz 📥
x264	18051	44780	5246565	13.02	x264_field_sensitive_alias.tar.gz 📥
cactus	22350	56636	37625324	0.112	cactus_field_sensitive_alias.tar.gz 📥
parest	29788	64528	49415038	0.145	parest_field_sensitive_alias.tar.gz 📥
perlbench	38091	110874	851737865	0.223	perlbench_field_sensitive_alias.tar.gz 📥
imagick	41652	111550	369956094	0.223	imagick_field_sensitive_alias.tar.gz 📥
omnetpp	49962	119064	158255766	0.260	omnetpp_field_sensitive_alias.tar.gz 📥

Canonical grammars

Productions with index \(i\) are duplicated for each field number from the analyzed program classes. The start nonterminal is \(V\). Reversed edges (a_r, d_r, f_r_i) are auto-generated from forward edges.

\[\begin{split}M \, \rightarrow \, d_r \, V \, d \, \\ V \, \rightarrow \, A_r \, V \mid V \, A \mid f_{r\_i} \, V \, f_i \mid M \mid \varepsilon \, \\ A_r \, \rightarrow \, M \, a_r \mid a_r \mid \varepsilon \, \\ A \, \rightarrow \, a \, M \mid a \mid \varepsilon \, \\\end{split}\]

RSM (stored as vf.rsm in each archive):

start: V
[box M]
start: 0
final: 3
0 --d_r--> 1
1 --V--> 2
2 --d--> 3
[box V]
start: 0
final: 0, 1, 2, 3, 4
0 --V--> 1
0 --M--> 4
0 --a_r--> 5
4 --a_r--> 5
5 --V--> 1
1 --a--> 2
2 --M--> 3
0 --f_r_i--> p_i
p_i --V--> q_i
q_i --f_i--> 3