Program Analysis for Modern Software Tools

About the Course Faculty

Dr Rajeev Barua is a Professor of Electrical and Computer Engineering at the University of Maryland. Dr Barua's research interests are in the areas of compilers, binary rewriters, embedded systems, and computer architecture. He has published over 60 peer-reviewed publications, and holds four granted patents. He is also the Founder of CEO of SecondWrite Inc, which markets a malware detection tool based on his research, where he has raised over $2M in public and private investment, and launched a product with several paying customers. Dr Barua is a recipient of the NSF CAREER award in 2002, the UMD George Corcoran Award for teaching excellence in 2003, and the UMD Jimmy Lin Award for innovation in 2014.

Program Analysis for Modern Software Tools

Course Description

Program analysis is the foundation of software tools that must understand, evaluate, or transform code. This course develops the representations and reasoning methods behind compilers, interpreters, debuggers, optimizers, bug and vulnerability detectors, malware-analysis systems, memory-error and performance-monitoring tools, and AI-assisted software development. Students learn how source text becomes structured program representations and how control-flow, dataflow, liveness, and SSA analyses derive useful facts and justify transformations. In an era of AI-generated code, these systematic methods complement probabilistic generation by helping developers reason about correctness, security, performance, and the capabilities and limitations of automated tools.

Course Overview and Relevance

Modern software tools do far more than translate or execute code. They inspect programs for defects, transform them for efficiency, instrument them for debugging and monitoring, and help developers understand and modify large software systems. To perform these tasks, tools must recover structure from source text, represent possible execution paths, track how values are defined and used, and reason conservatively about program behavior. Related foundations recur across compilers and interpreters, static bug and vulnerability analyzers, malware and binary-analysis systems, memory diagnostics, debuggers and profilers, performance-monitoring systems, IDE refactoring and code-navigation features, and automated software-transformation tools.

INTELLECTUAL PROGRESSION:  Source text > tokens and syntax > intermediate representation > control flow > dataflow facts > justified transformations > SSA and aliasing

Students learn to read program representations, perform analysis algorithms manually, and determine when transformations are justified. The goal is not familiarity with the API of one framework. It is mastery of durable concepts that transfer across languages, toolchains, security products, developer tools, and future systems. Students will not build a production analyzer in five days, but they will acquire the foundation needed to understand, evaluate, use intelligently, and later help build program-analysis-based tools.

Generative AI changes the scale and speed at which software can be produced, but not the need to reason about it. AI-generated code still has syntax, control flow, definitions, uses, live values, and aliases, and plausible-looking code may still be incorrect, insecure, or inefficient. Program analysis complements probabilistic generation with structured reasoning about the actual program. Such reasoning can help ground AI coding assistants and agents and provide quality and security checks around generated code. Related ideas also appear in the translation and optimization stacks used by AI systems. The course does not teach LLM engineering or AI-based program analysis; it provides foundations that students can later combine with those technologies.

Intended Audience and Required Background

The course is designed for senior undergraduate students in Computer Science and Artificial Intelligence. It is particularly relevant to students interested in software engineering, AI-assisted software development, compilers and programming languages, cybersecurity, developer tools, software reliability, performance engineering, systems, or automated reasoning about code.

Students should be comfortable programming in a conventional imperative language and reading small C or C++ examples. Familiarity with functions, variables, expressions, conditionals, loops, basic data structures, and elementary mathematical notation is expected. Prior coursework in compilers, formal languages, program analysis, or advanced C++ is not required.

Course Learning Outcomes

CLO1 - Understand. Distinguish compilation from interpretation and explain the roles of compilers, assemblers, linkers, loaders, debuggers, object code, machine code, and intermediate representations.

CLO2 - Apply / Analyze. Classify representative source fragments into tokens; interpret regular expressions and finite automata; apply longest-match and rule-priority conventions; and explain why finite-state methods cannot recognize unbounded nesting.

CLO3 - Apply / Analyze. Interpret context-free-grammar productions, derivations, and parse trees; identify ambiguity; and determine how grammar structure expresses precedence and associativity.

CLO4 - Analyze. Read simple intermediate representations and identify basic blocks, control-flow relationships, call relationships, loops, and dominance.

CLO5 - Apply / Analyze. Formulate and manually solve reaching-definitions and liveness analyses using gen, kill, in, and out sets together with iterative fixed-point computation.

CLO6 - Analyze / Evaluate. Use program structure and analysis results to identify and justify constant propagation, constant folding, control-flow simplification, copy propagation, and dead-code elimination.

CLO7 - Analyze / Evaluate. Interpret SSA names and simple phi functions, explain how SSA simplifies transformations, and analyze how pointers, aliases, and address-taken variables complicate sound analysis.

CLO-PLO Mapping Status 

BOARD-REVIEW PLACEHOLDER:  The formal undergraduate CSAI program learning outcomes have not yet been supplied or verified. The Master's of Science in AI PLOs contained in an illustrative syllabus are not applicable to this undergraduate course. A CLO-PLO map will be completed after Plaksha provides or confirms the approved BTech CSAI PLOs.

Course Structure and Topic Sequence

The ten topics form a continuous progression in how software tools recover, represent, and reason about programs. The course begins by turning source text into tokens and grammatical structure, moves from that structure to intermediate representations and possible control flow, and then develops analyses that compute program facts and use them to justify transformations. It concludes with SSA, which makes data dependencies more explicit, and memory aliases, which reveal a fundamental limitation of automated reasoning about real programs.

No. Topic Primary focus
No.

1

Topic

Program Translation and the Software Toolchain

Primary focus

Compilation and interpretation; machine and object code; assemblers, linkers, loaders, debuggers, and intermediate representations.

No.

2

Topic

Lexical Analysis and Regular Expressions

Primary focus

Token classes, lexical patterns, regular expressions, and the longest-match and rule-priority conventions.

No.

3

Topic

Finite Automata and the Limits of Regular Expressions

Primary focus

Finite-state recognition and the inability of regular languages to express unbounded nesting.

No.

4

Topic

Context-Free Grammars, Derivations, and Parse Trees

Primary focus

Grammar productions, terminals and nonterminals, derivations, and parse-tree structure.

No.

5

Topic

Ambiguity, Precedence, and Associativity

Primary focus

Ambiguous parses and the way grammar structure encodes operator precedence and associativity.

No.

6

Topic

Intermediate Representation and Control-Flow Structure

Primary focus

Basic blocks, control-flow and call relationships, loops, and dominance.

No.

7

Topic

Reaching Definitions and Dataflow Formulation

Primary focus

Definitions and uses; gen, kill, in, and out equations for reaching definitions.

No.

8

Topic

Fixed-Point Dataflow and Reaching-Definition Transformations

Primary focus

Iterative convergence; constant propagation and folding, control-flow simplification, and copy propagation.

No.

9

Topic

Liveness, Dead-Code Elimination, and the Motivation for SSA

Primary focus

Backward liveness equations, dead-code elimination, and why explicit definition-use structure helps.

No.

10

Topic

SSA Form, SSA Transformations, and Memory Aliases

Primary focus

SSA names and phi functions; transformations in SSA; pointers, aliases, address-taken variables, and memory.

Course Format

Class meetings combine focused lectures, worked examples, and guided analytical problem solving. Students practice translating between program representations, applying analysis equations, following fixed-point computations, and defending whether transformations are justified. The course is conceptually and algorithmically rigorous, with emphasis on portable methods that transfer across languages, toolchains, security products, and developer tools. Each three-hour meeting includes one 10-minute break.

Assessment and Grading

Mastering program-analysis methods requires repeated practice rather than passive familiarity. The five short homeworks provide daily practice with the representations and algorithms introduced in class. The two in-class proctored quizzes provide the primary evidence of each student's independent mastery. Attendance reflects the cumulative nature of an intensive course in which each meeting accounts for one fifth of the total contact time. There are no programming assignments or other graded in-class assessments.

Component Number Weight per item/day Total
Component

Homework

Number

5

Weight per item/day

5% each

Total

25%

Component

Attendance

Number

5 days

Weight per item/day

4% per day

Total

20%

Component

Quiz 1

Number

1

Weight per item/day

27.5%

Total

27.5%

Component

Quiz 2

Number

1

Weight per item/day

27.5%

Total

27.5%

Component

Total

Number Weight per item/day Total

100%

Homework: Five short, individual theory homeworks are assigned on Days 1-5 and submitted online the following day. Homework 5 is due online on Saturday, December 19, 2026. Homework provides frequent practice but is lower-stakes than the proctored quizzes.

Quiz 1. A 20-minute, in-class, proctored, non-programming quiz held in the first 20 minutes of Day 3. It covers material taught on Days 1 and 2.

Quiz 2. A 20-minute, in-class, proctored, non-programming quiz held in the final 20 minutes of Day 5. It covers material taught on Days 3 and 4; material first introduced on Day 5 is not tested.

Attendance. Attendance is recorded each day and contributes 4% per meeting, for 20% in total. The detailed attendance and documented-circumstance policy appears below.

Workload and Preparation 

EXPECTED OUT-OF-CLASS WORK:  Students should expect approximately 8-10 hours of work outside scheduled class meetings across the entire course. This includes the five short homeworks, review of lecture material, and preparation for the two quizzes.

Students should attend all five meetings, complete each daily homework, review the preceding day's terminology and representations before the quizzes, and engage actively with worked examples and guided reasoning. There is no separate participation percentage.

Five-Day Class Schedule

The course meets Monday through Friday, December 14-18, 2026, for one three-hour class each day. Each meeting includes one 10-minute break. The sequence below preserves the final ten-topic architecture and shows what students know before each quiz.

Day Theme Key concepts and activities Assessment work
Day

Day 1 Monday, Dec 14, 2026

Theme

How tools translate and structure source code

Key concepts and activities

Program translation and interpretation; the software toolchain; machine code, object code, intermediate representations, linking, loading, and debugging. Lexical analysis; token classes; regular expressions; longest-match and rule-priority conventions.

Assessment work

Homework 1 assigned; due online on Day 2.

Day

Day 2 Tuesday, Dec 15, 2026

Theme

From token patterns to program structure

Key concepts and activities

Finite automata and the limits of regular expressions. Context-free grammars; terminals and nonterminals; productions, derivations, and parse trees. Ambiguity, precedence, and associativity.

Assessment work

Homework 1 due; Homework 2 assigned. Prepare for Quiz 1.

Day

Day 3 Wednesday, Dec 16, 2026

Theme

Representing possible execution and dataflow

Key concepts and activities

After Quiz 1: final parsing example; intermediate representation; basic blocks; control-flow and call graphs; loops; dominance; definitions and uses; reaching definitions; gen, kill, in, and out sets.

Assessment work

First 20 minutes: Quiz 1 (Days 1-2). Homework 2 due; Homework 3 assigned.

Day

Day 4 Thursday, Dec 17, 2026

Theme

Computing program facts and using them safely

Key concepts and activities

Iterative fixed-point computation and convergence. Constant propagation and folding, control-flow simplification, and copy propagation. Liveness, dead-code elimination, and the motivation for SSA.

Assessment work

Homework 3 due; Homework 4 assigned. Prepare for Quiz 2.

Day

Day 5 Friday, Dec 18, 2026

Theme

Making dependencies explicit: SSA and memory aliases

Key concepts and activities

SSA names and phi functions; transformations in SSA; pointer stores; aliases; address-taken variables; demotion to memory; and course synthesis.

Assessment work

Homework 4 due; Homework 5 assigned. Final 20 minutes: Quiz 2 (Days 3-4). Homework 5 due Sat., Dec. 19.