Using a dependency graph to evaluate Terraform configuration in static analysis

[nikpivkin]

Description

Current evaluation model

In the current model, all configuration blocks are evaluated sequentially and repeatedly - pass after pass - until the values in the context stabilize (stop changing).

How it works:

• A full traversal of all blocks is performed and their values are computed.
• The results are stored in a context.
• If any value changes during a pass, another traversal is started.
• This process repeats until values no longer change between passes.

Drawbacks of the iterative model:

• Redundant calculations: Many blocks may be recalculated multiple times even after their values have stabilized.

• Potentially long running time: For large configurations with complex dependencies, many passes may be needed.

• Difficult to control evaluation order: There is no strict computation order, making it hard to determine which blocks influence the result at any point.

There are a few issues that are hard to solve:

• fix(terraform): 'count' meta argument sourced from submodule output #8899
• test: eagerly loaded locals can cause incorrectly ordered execution #9139
• `for_each` over a map returns a resource for every key on the object #9155 (fixed)

Proposal

Implement configuration evaluation by building a block dependency graph based on implicit dependencies extracted from expressions (references to resources, variables, locals, modules, etc).

Options

1. Full graph with topological sorting

In this approach, a complete dependency graph between blocks is constructed, and all blocks are evaluated in topological order.

Pros:

• Predictable, deterministic evaluation order.
• Easy to detect cycles and perform full value export.

Minuses:

• All blocks must be computed even if only some values are needed.

2. Lazy on-demand evaluation

Block values are computed only by explicit request. Missing dependencies are recursively calculated and cached.

Pros:

• Resource efficient: only necessary blocks are evaluated.
• Flexible for partial evaluation and complex use cases.

Minuses:

• Cycle detection and debugging are more challenging.
• Tracking overall evaluation order and understanding the full computation flow is harder.

3. Hybrid approach

The hybrid approach involves building the complete dependency graph upfront without performing immediate computations. Evaluation is done lazily, with caching of computed values triggered only when specific values are requested. Additionally, it supports full graph traversal and evaluation of all blocks on demand or by using an explicit flag.

Benefits:

• Balances performance with predictability.
• Provides flexibility across different usage scenarios.
• Simplifies cycle detection and debugging.

Key points for Implementation

• Each graph node (block) must have a unique identifier for unambiguous referencing.
• Split locals into separate blocks with type local and the name of each local variable; this is necessary because local variables can reference themselves or each other.
• Only consider the default expression in variable blocks for evaluation.
• Extract dependencies by analyzing hcl.Traversal expressions.
• Implement caching and computation tracking to avoid infinite loops and redundant calculations.

Target

None

Scanner

Misconfiguration

[Emyrk]

This can also resolve/change a behavior in how count is evaluated today. A block with a count of an unknown value is set to 1.

https://github.com/coder/trivy/blob/12d6706961423acb12430c8b3d986b4aa4671d04/pkg/iac/scanners/terraform/parser/evaluator.go#L417

With a DAG, that unknown value does not need to be prematurely expanded. Once the DAG eval "stops" or stalemates, remaining unexpanded blocks could be handled differently. Or at least marked in such a way that it is known the count is not known.

At present, it can hide unintentional issues.