When an analyst asks “what can affect this dangerous call”, they are really asking a graph question. A program dependence graph answers it. It is a way to draw a function so that the edges show which statements feed which other statements, and which statements only run because of a branch. Once you have that picture, you can start at any line and read off exactly what influences it.
What a program dependence graph is
A program dependence graph has one node per statement and two kinds of edge. That is the whole idea. The value of the graph is that it drops the parts of a program that do not matter for a given question and keeps the parts that do.
- Data dependence. Statement B uses a value that statement A defined. If A writes
totaland B readstotalwith no other write in between, there is a data dependence edge from A to B. - Control dependence. Whether statement B runs at all depends on a branch condition at statement A. If B sits inside an
ifand the test at A decides whether that body executes, there is a control dependence edge from A to B.
Regular source code hides both of these behind line order. Line 8 might depend on line 2 and ignore lines 3 through 7 completely. The program dependence graph makes that real relationship explicit so you do not have to hold it in your head.
A small function, edge by edge
Here is a short function that charges a user. Read it once, then we will label every statement and list its edges.
def charge(user_id, amount):
balance = get_balance(user_id) # S1
fee = amount * 0.02 # S2
total = amount + fee # S3
if balance >= total: # S4
record = build_record(user_id, total) # S5
db.execute(record) # S6
return total # S7The data dependence edges
Follow each value from where it is written to where it is read.
S3readsfee, so S2 to S3.S4readsbalanceandtotal, so S1 to S4 and S3 to S4.S5readstotal, so S3 to S5.S6readsrecord, so S5 to S6.S7readstotal, so S3 to S7.
The two parameters, user_id and amount, are the roots. They feed S1, S2, and S5 directly.
The control dependence edges
Now ask which statements only run because a test allowed them to.
S5andS6live inside theifatS4. So S4 to S5 and S4 to S6.S1,S2,S3,S4, andS7run every time the function is called. They have no control dependence inside this function.
Notice that data and control are different questions with different answers. S6 has no data edge from S4, because it does not read the boolean the test produced. But it has a control edge from S4, because the branch decides whether S6 happens at all. Miss either edge type and your picture of the function is wrong.
Program slicing: reading the graph backward and forward
Once the edges exist, slicing is just a walk. A backward slice from a statement follows dependence edges in reverse to collect every statement that can affect it. A forward slice follows edges the other way to collect everything that statement affects.
Take the backward slice from S6, the database call. Walk the edges into it and keep going.
S6pulls inS5by data andS4by control.S5pulls inS3by data andS4by control.S4pulls inS1andS3by data.S3pulls inS2by data.S2andS1pull in the parameters.
The backward slice from S6 is {S1, S2, S3, S4, S5} plus both parameters. Look at what fell out: S7, the return total. It reads total, so it is part of the function, but nothing about it can change what S6 does. The slice removed it correctly. You now hold the smallest set of statements that decides the behavior of that one call.
A backward slice from a dangerous call is a complete, honest answer to “what can influence this line”, with the unrelated code already deleted.
Why the program dependence graph matters for security
An analyst looking at a risky operation asks one question first. What reaches this? If db.execute can run attacker controlled text, that is a possible injection. If it cannot, the call is fine. The backward slice from that sink is exactly that answer, computed instead of guessed.
Say a request handler ends in a raw query. The backward slice tells you every statement between the request parameter and the query string. If a validation step or an escaping call sits on that slice, the input is checked before it reaches the sink. If the slice runs from the parameter straight into the query with nothing in between, you have found the shape of a real bug. The graph turns a vague worry into a finite list of statements to read.
Control dependence carries its own weight here. An access check is usually an if that guards the sensitive action. If the sink has no control edge from that check, the check does not actually gate it, and the guard is decorative. That gap is the kind of thing a scanner that only matches text will walk right past. For more on why understanding an app beats matching patterns, read scanners vs research.
Where it sits in the bigger picture
The program dependence graph is not the whole story on its own. It is one layer that a richer structure merges together. A code property graph stitches the syntax tree, the control flow graph, and the program dependence graph into a single queryable model, so you can ask about structure and dependence in one place.
Slicing also assumes you already know where each value is defined and used, across function calls and reassignments. Computing that is the job of data flow analysis, which works out the definitions that can reach each use. The program dependence graph is the map. Data flow analysis is how the map gets drawn.
The takeaway
Two edge types, one node per statement, and a walk in either direction. That is enough to answer the question an analyst cares about most: given a dangerous call, show me only the code that can steer it. A backward slice from a sink hands you that set with nothing extra to read. This is the kind of structural reasoning UnboundCompute leans on when it studies how an app is meant to work and looks for the assumptions that quietly fail. You can read more about that approach on our about page.
Frequently asked questions
What are the two kinds of edge in a program dependence graph?
A program dependence graph has data dependence edges and control dependence edges. A data dependence edge runs from statement A to statement B when B reads a value that A defined. A control dependence edge runs from a branch at A to B when the test at A decides whether B runs at all. One node per statement, two edge types, and that is the whole model.
What is program slicing?
Slicing is a walk over the dependence edges. A backward slice starts at one statement and follows edges in reverse to collect every statement that can affect it. A forward slice follows edges the other way to collect everything that statement affects. The result is the smallest set of statements that matters for the question you asked.
Why is a backward slice useful for security?
A backward slice from a dangerous call, such as a database query or a shell command, is exactly the set of statements that can influence that call. If the slice runs from a request parameter straight into the sink with no validation or escaping on the way, you have found the shape of an injection bug. If a check sits on the slice, the input is gated before it reaches the sink.
How does the program dependence graph relate to a code property graph?
The program dependence graph is one of the layers a code property graph merges. A code property graph stitches the syntax tree, the control flow graph, and the program dependence graph into a single model you can query, so you can ask about structure and dependence at the same time. Data flow analysis is what computes the definitions and uses that the dependence edges rest on.
Put an autonomous researcher on your own systems
UnboundCompute is an autonomous security researcher that reasons about how an application fits together and proves the access control and injection bugs it finds. We are opening a small number of founding design partner seats: private early access pointed at a staging target you choose, and a say in what it looks for. If your team ships software worth pressure testing, apply to the design partner program.