Dependency Graph

A dependency graph is strictly directed and ideally acyclic. Edges point from a dependent package to its dependency. The acyclic property prevents circular references (e.g., Package A requiring Package B, which requires Package A), which would cause infinite loops in resolvers. Resolution algorithms like those in pip or npm perform topological sorting to determine a valid, flat installation order from this graph. In machine learning pipelines, this structure maps not just Python packages but also model weights, tokenizers, and preprocessing scripts.

The graph captures not just direct dependencies but the full transitive closure—the complete tree of all nested requirements. A single top-level import of transformers can pull in hundreds of sub-dependencies. This is critical for security because a vulnerability in a deeply nested, indirect dependency (e.g., a logging library six levels deep) is invisible without graph traversal. Tools like Software Composition Analysis (SCA) scanners walk this transitive graph to identify known Common Vulnerabilities and Exposures (CVEs) across the entire supply chain.

Each edge in the graph carries a version constraint (e.g., >=1.0.0, <2.0.0 or ~=3.2.1). The dependency resolver must find a set of concrete versions that satisfies all constraints simultaneously—a problem known as version set solving, which is NP-complete in the general case. In AI supply chains, conflicting version constraints on shared libraries like NumPy or protobuf are a frequent source of dependency hell, leading to brittle, non-reproducible builds. The graph makes these conflicts explicit and traceable.

A complete dependency graph distinguishes between build-time and runtime dependencies. Build dependencies (e.g., compilers, code generators, CUDA toolkits) are required only during model training or artifact compilation. Runtime dependencies (e.g., inference servers, ONNX runtimes) are needed in production. This separation is crucial for minimizing the attack surface of deployed AI systems. A production container should exclude build tools to prevent an attacker from compiling malicious payloads post-exploitation.

Modern dependency graphs associate each resolved node with a cryptographic content hash (e.g., SHA-256). This transforms the graph from a purely logical map into a verifiable integrity record. When combined with a lockfile (e.g., poetry.lock, package-lock.json), the graph pins every transitive dependency to an exact, immutable artifact. Any tampering—such as a dependency confusion attack substituting a malicious package—is immediately detectable because the hash of the downloaded artifact will not match the graph's recorded hash.

During a zero-day vulnerability disclosure (e.g., a critical CVE in a common library like log4j or pillow), the dependency graph becomes an incident response tool. Security engineers query the graph to instantly identify every affected path—every top-level project that transitively depends on the vulnerable component. This enables precise, surgical remediation rather than blanket upgrades. Graph databases and tools like Graphviz render these dependency trees, highlighting the vulnerable node and all inbound dependency paths.

The algorithmic process of resolving a package's indirect dependencies—the dependencies of your dependencies. A dependency graph makes these hidden relationships explicit, revealing vulnerabilities buried deep in the tree.

• A single direct dependency can pull in hundreds of transitive packages
• Version conflict resolution uses strategies like semantic versioning and lock files
• Attackers target transitive dependencies because they are rarely audited directly

A supply chain attack vector exploiting the resolution algorithm of dependency graphs. An attacker uploads a malicious package with a higher version number to a public registry, tricking the build system into downloading it instead of the intended private dependency.

• Also known as a namespace confusion or substitution attack
• Mitigated by scoped registries and explicit source declaration
• Discovered by security researcher Alex Birsan in 2021, affecting Apple, Microsoft, and Tesla

An automated process that scans a codebase to identify and catalog all open-source components, mapping them into a dependency graph for vulnerability and license risk assessment.

• Cross-references component versions against databases like NVD and GitHub Advisory Database
• Detects outdated libraries and copyleft license conflicts
• Integrates directly into CI/CD pipelines for continuous monitoring

The practice of locking every dependency in the graph to an exact, immutable version or cryptographic hash. Lock files like package-lock.json or Cargo.lock freeze the entire resolved graph to guarantee reproducible builds.

• Prevents supply chain drift where upstream changes break builds
• Essential for deterministic CI/CD pipelines and auditability
• Must be regularly updated to incorporate security patches without introducing unexpected mutations