C alias analysis

Release:

6.1.2

Date:

Oct 28, 2026

Points-to (alias) graphs for a suite of C programs, built by demand-driven alias analysis as in “Demand-driven alias analysis for C”. Nodes are program entities and edges are the aliasing and flow relations discovered for each program.

Graph	Num Nodes	Num Edges	Reachable pairs	Size (MB)	Download
wc	332	269	156	0.003	wc.tar.gz 📥
bzip	632	556	315	0.005	bzip.tar.gz 📥
pr	815	692	385	0.006	pr.tar.gz 📥
ls	1687	1453	854	0.011	ls.tar.gz 📥
gzip	2687	2293	1458	0.017	gzip.tar.gz 📥
apache	1721418	1510411	92806768	9.05	apache.tar.gz 📥
init	2446224	2112809	3783769	12.84	init.tar.gz 📥
mm	2538243	2191079	3990305	13.33	mm.tar.gz 📥
ipc	3401022	2931498	5249389	18.01	ipc.tar.gz 📥
lib	3401355	2931880	5276303	18.01	lib.tar.gz 📥
block	3423234	2951393	5351409	18.14	block.tar.gz 📥
arch	3448422	2970242	5339563	18.25	arch.tar.gz 📥
crypto	3464970	2988387	5428237	18.38	crypto.tar.gz 📥
security	3479982	3003326	5593387	18.47	security.tar.gz 📥
sound	3528861	3049732	6085269	18.77	sound.tar.gz 📥
net	4039470	3500141	8833403	21.66	net.tar.gz 📥
fs	4177416	3609373	9646475	22.34	fs.tar.gz 📥
drivers	4273803	3707769	18825025	22.99	drivers.tar.gz 📥
postgre	5203419	4678543	90661446	29.37	postgre.tar.gz 📥
kernel	11254434	9484213	16747731	59.99	kernel.tar.gz 📥

Canonical grammars

Note

In order to get the original graph you must apply function change_edges with mapping={"a": "A", "d": "D"} to this graph. In this case these grammars must be updated.

Grammars for the alias analysis of C programs introduced in “Demand-driven alias analysis for C”. Template for these grammars is described on the C Alias page.

\[\begin{split}S \, \rightarrow \, d_r \, V \, d \, \\ V \, \rightarrow \, V_1 \, V_2 \, V_3 \, \\ V_1 \, \rightarrow \, \varepsilon \, \\ V_1 \, \rightarrow \, V_2 \, a_r \, V_1 \, \\ V_2 \, \rightarrow \, \varepsilon \, \\ V_2 \, \rightarrow \, S \, \\ V_3 \, \rightarrow \, \varepsilon \, \\ V_3 \, \rightarrow \, a \, V_2 \, V_3 \, \\\end{split}\]

Pyformlang CFG:

S -> d_r V d
V -> V1 V2 V3
V1 -> epsilon
V1 -> V2 a_r V1
V2 -> epsilon
V2 -> S
V3 -> epsilon
V3 -> a V2 V3

---

\[\begin{split}S \, \rightarrow \, d_r \, V \, d \, \\ V \, \rightarrow \, ((S \mid \varepsilon) \, a_r)^{*} \, (S \mid \varepsilon) \, (a \, (S \mid \varepsilon))^{*} \, \\\end{split}\]

Pyformlang RSA:

S -> d_r V d
V -> ((S|epsilon) a_r)* (S|epsilon) (a (S|epsilon))*

Optimized variant

An equivalent WCNF grammar introduced as optimization (5) in “Optimization of the Context-Free Language Reachability Matrix-Based Algorithm” (Fig. 2(b)) is stored in each archive as c_alias_muravev2024.cnf. It generates the same language and returns identical reachable-pair counts (verified with FastMatrixCFPQ on small graphs).

M    N1      N3
M    N2      N3
N1   d_r
N1   N1      a_r
N1   N2      a_r
N2   N1      M
N3   d
N3   a       N3
N3   AM      N3
AM   a       M

Count:
M