Motivation / Problem
Currently, if a malicious upstream policy source wants to use excessive memory (or cause an OOM!) in a Swift OPA IR evaluator, all they have to do is simply add an IR instruction into a Plan with a ridiculous Local index, like so:
AssignIntStmt int64(0), 2147483647
// ^^^^^^^^^^^^^ ^^^^^^^^ ^^^^^^^^^^
// instr source target
In any IR plan, we should be able to trivially rewrite the plan so that all of the Local indices (register numbers) are contiguous within a given IR Plan/Func. This can be done in 1-2x linear scans over the IR instructions in the plan.
Proposed Solution
We should add a new IR static analysis pass that runs before (or as part of!) the computeMaxLocal function. The new pass will do the 1-2x scans over the IR, tracking seen indexes, and performing index remapping as necessary.
The end result will have a contiguous set of Local indexes across the Plan/Func.
This strongly bounds how many "dead indexes" are possible when we allocate arrays later on for Locals storage in the IR evaluator.
Single-scan, naive remap
A naive method would be to use a counter variable and a dictionary of [Int: Int], bumping up the counter variable as new contiguous indexes are seen in the policy. As remappings occur, the dictionary accrues more entries. This could result in excessive remapping in some cases.
2-scan, cleaner remap
A less naive, 2-pass method would be to scan over the instructions in the Plan/Func, and track every index seen, then a second pass would perform the remapping optimally, avoiding spurious remappings at lower index values.
Related Resources
- Register renaming: A range of hardware techniques for dynamically remapping registers at execution time.
- Register allocation: A field of compiler techniques for mapping N-many logical registers onto a limited set of physical registers.
How to test?
Tests could be built around fuzzers generating/mutating the indexes in normal policies, and would check that the final list of "seen indexes" in the renumbered IR are contiguous.
Motivation / Problem
Currently, if a malicious upstream policy source wants to use excessive memory (or cause an OOM!) in a Swift OPA IR evaluator, all they have to do is simply add an IR instruction into a Plan with a ridiculous
Localindex, like so:In any IR plan, we should be able to trivially rewrite the plan so that all of the
Localindices (register numbers) are contiguous within a given IR Plan/Func. This can be done in 1-2x linear scans over the IR instructions in the plan.Proposed Solution
We should add a new IR static analysis pass that runs before (or as part of!) the
computeMaxLocalfunction. The new pass will do the 1-2x scans over the IR, tracking seen indexes, and performing index remapping as necessary.The end result will have a contiguous set of
Localindexes across the Plan/Func.This strongly bounds how many "dead indexes" are possible when we allocate arrays later on for Locals storage in the IR evaluator.
Single-scan, naive remap
A naive method would be to use a counter variable and a dictionary of
[Int: Int], bumping up the counter variable as new contiguous indexes are seen in the policy. As remappings occur, the dictionary accrues more entries. This could result in excessive remapping in some cases.2-scan, cleaner remap
A less naive, 2-pass method would be to scan over the instructions in the Plan/Func, and track every index seen, then a second pass would perform the remapping optimally, avoiding spurious remappings at lower index values.
Related Resources
How to test?
Tests could be built around fuzzers generating/mutating the indexes in normal policies, and would check that the final list of "seen indexes" in the renumbered IR are contiguous.