What is a program analysis technique for tracing assignments (mutations)?

Question

I am looking to write a program analysis for Java programs that tracks assignments and is able to discern:

• whether a class field (static or not) is read and where the read originated
• whether a class field (static or not) is written and where the write originated
• properties of the value that is written: 1) is it a scalar 2) is the result of a composite expression (e.g. arithmetic expression or some other composite expression that involves applying operators to some operands)

This will need some sort of dependency resolution surrounding reads and writes to variables and (time permitting) consider variable aliasing as well.

I have been searching for various phrases that involve keywords "mutation" and "writes" but the results target mutation testing and other things that are not what I am looking for.

What is a technique or a class of techniques that fits these types of analyses and is there a fundamental technique that I can get started with?

Answer 1

There are many techniques, with differing tradeoffs between the precision of the results vs the simplicity and running time of the algorithm.

I suggest looking at class hierarchy analysis (CHA), rapid type analysis (RTA), points-to analysis (e.g., Steensgaard's algorithm, Andersen's algorithm, and more), and more generally, alias analysis. You'll find a gazillion papers on these topics.

Note that in general this is an undecidable problem, so any analysis will output results that are an overapproximation (sound). Also, there are some complicated cases that for engineering reasons most analyses ignore (e.g., reflection).