Skip to content

[crypto] Improve static analysis for instruction count bounding #137

@pqcfox

Description

@pqcfox

Description

Currently, the static analysis tooling used in hw/ip/otbn/util/gen_instruction_count_headers.py is functional, but there are some major areas for improvement that could allow tighter bounding:

  1. Some bounds aren't tight due to limitations of the current approach of collecting maximum and minimum loop iteration counts using constant propagation during information flow analysis, and then afterward using those count ranges to compute.
  2. Because constant propagation across loops requires that registers holding constants not be sinks in the information flow sense, constants which are clobbered and then restored are not tracked as loop invariants by the current information flow analysis logic.

For (1), a more tightly coupled information flow analysis and instruction count bounding process could achieve tighter bounds by making use of the additional control flow information available while bounding.

For (2), detecting restoration of constants by checking propagated constant values instead of detecting sinks could be one approach.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions