python-igraph C Extension Analysis Report

Development
1

Hello,

I ran a code review tool I develop on igraph and got interesting results from it. Below’s an overview, and the full report is available at python-igraph C Extension Analysis Report · GitHub. I hope it helps.

Please let me know if you’d like me to open an umbrella issue, individual issues, PRs or if there’s any other kind of way to help.

python-igraph Analysis

48 FIX, 30 CONSIDER, 8 POLICY from 13 agents + clang-tidy/cppcheck.

Key Statistics

Category Count Most Severe
Crash bugs (use-after-free, segfault, NULL deref) 13 _enter_safelocale returns dangling > pointer; 3 functions use freed weights
__new__ segfaults 6 types Vertex (22 methods crash), EdgeSeq (len() crashes)
Reference leaks 12 Per-iteration leak in adjacency matrix (1 int per edge per call)
igraph resource leaks 8 BFS wrong-variable + triple vector leak
Re-init safety 5 types All leak gref/destructor/selectors
PyErr_Clear 6 findings Preemptive clear in hot Py_mp_subscript path

What’s Good

  • Exemplary stable ABI implementation — zero production-code violations at Python 3.9
  • All 8 types use PyType_FromSpec with correct heap-type dealloc
  • Graph type has explicit __new__ safety — developer comment shows awareness
  • RNG callbacks correctly use PyErr_WriteUnraisable — best practice for error-constrained > callbacks

Dominant Bug Patterns

  1. Error-path resource cleanup — The most common class. igraph vectors/matrices allocated before an igraph call are not freed when the call fails. The graphobject.c monster (19K lines) has hundreds of such allocation/call/cleanup sequences.

  2. Code cloning — VertexSeq/EdgeSeq duplication already caused a proven divergent refcount bug (EdgeSeq has Py_DECREF(result) at line 725, VertexSeq doesn’t at line 703).

  3. __new__-without-__init__ — 6 of 8 types crash because gref (graph back-pointer) is NULL after zero-fill allocation. The CHECK_GRAPH(self) macro approach would fix most with minimal code changes.

python-igraph Reproduction

13 findings reproduced, 35 code-confirmed.

Reproduction Highlights

Category Count Most Dramatic
Segfaults from __new__ 7 Vertex.graph, Edge.graph, EdgeSeq len(), VertexSeq.graph, EdgeSeq.graph, Vertex.degree(), Edge.is_loop()
Segfaults via OOM injection 3 feedback_arc_set(weights=...) at set_nomemory(1,0), feedback_vertex_set same, contract_vertices at set_nomemory(3,0)
MemoryError swallowed 2 g.vs[BadIndex()] and g.get_shortest_paths(BadVid()) — both replace MemoryError with generic TypeError
Reference leaks 2 Vertex re-init (1.7KB/200), Graph re-init (6.8KB/200)
SystemError 1 len(VertexSeq.__new__(VertexSeq)) — returns NULL without exception
2

Thanks for taking the time to do this.

I’ll leave commenting on Python-specific issues to @tamas.

If you have reproducers for these bugs, it would indeed be nice to open issues. I’d suggest starting small and opening just one or two issues at first for problems that seem the most straightforward. I think it’ll be worth working through them before opening issues for everything.

Is your tool specifically for Python extensions or does it support C as well? If it supports C, can you run it on the core igraph C library? If it’s easier to do this through Python, can you run it in a way that it would analyse the vendored C library source code while analysing python-igraph?

Note: I’m overwhelmed at the moment (had have been for some months) and will need time until I can give the problems a careful look.

3

Thank you for being receptive and for the guidance.

This toolkit is specifically designed for the Python/C API boundary: it mostly finds reference counting bugs, exception handling issues, GIL discipline problems, type slot correctness, etc.

So running it on the core igraph C library doesn’t produce many interesting results. Still, here’s the summary of what it was able to find:

  • 1 buffer overflow (DRL 3D layout — writes 3 coords into 2-element buffer)

  • 1 silent NaN (diversity with all-zero weights, reproduced in Python)

  • 49 unchecked push_back calls — the same pattern already fixed 6 times elsewhere

  • 26 unchecked allocations including 6 in Dijkstra and several in I/O parsers handling untrusted input

  • 37 unchecked allocations in vendored Cliquer

The full report for the C library is at igraph C Library Analysis Report · GitHub . I hope it helps.

A general C review toolkit is something I’m considering for the future and the igraph C library would be a great candidate to test against.

4

The analysis is correct. Technically a bug in the borrowed DrL code, but does not affect igraph, which does not use MPI with DrL. Fixed, and reduced MAX_PROC (max MPI processor count) to 1 to save a bit of stack space.

This is intended.

Can you get it to say where exactly these issues are instead of just giving a generic description? I fixed some, determined that some were invalid (where I added comments to make this clear), but I could not find all of them.

I suspect that the claims of unchecked IGRAPH_CALLOCs are incorrect, but I’m not sure. Can you get it to say where these are?

That’s likely true, but since this is borrowed / vendored code, and triggering this issue is extremely unlikely, I’d rather not touch it.

5

I asked it to give us a line-by-line map and indeed the claims were incorrect, sorry for not screening that enough.

Here’s the response:

Unchecked IGRAPH_CALLOC/IGRAPH_MALLOC — correction

Our initial report claimed 26 unchecked allocations. On detailed line-by-line verification, all 251 IGRAPH_CALLOC/IGRAPH_MALLOC calls are properly checked (with IGRAPH_CHECK_OOM or equivalent). The 2 unchecked calls in io/graphml.c are deliberately unchecked with graceful fallback. The “26 unchecked” figure from the git history agent was an overcount — we apologize for the inaccuracy.

Unchecked igraph_vector_int_push_back() — 51 calls in 5 files

games/erdos_renyi.c (16 calls)


line 343: igraph_vector_int_push_back(&edges, from);

line 344: igraph_vector_int_push_back(&edges, to);

line 354: igraph_vector_int_push_back(&edges, from);

line 355: igraph_vector_int_push_back(&edges, to);

line 362: igraph_vector_int_push_back(&edges, from);

line 363: igraph_vector_int_push_back(&edges, to);

line 370: igraph_vector_int_push_back(&edges, from);

line 371: igraph_vector_int_push_back(&edges, to);

line 810: igraph_vector_int_push_back(&edges, from);

line 811: igraph_vector_int_push_back(&edges, to);

line 821: igraph_vector_int_push_back(&edges, from);

line 822: igraph_vector_int_push_back(&edges, to);

line 829: igraph_vector_int_push_back(&edges, from);

line 830: igraph_vector_int_push_back(&edges, to);

line 837: igraph_vector_int_push_back(&edges, from);

line 838: igraph_vector_int_push_back(&edges, to);

games/sbm.c (14 calls)


line 170: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 171: igraph_vector_int_push_back(&edges, tooff + vto);

line 181: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 182: igraph_vector_int_push_back(&edges, tooff + vto);

line 195: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 196: igraph_vector_int_push_back(&edges, tooff + vto);

line 206: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 207: igraph_vector_int_push_back(&edges, tooff + vto);

line 217: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 218: igraph_vector_int_push_back(&edges, tooff + vto);

line 228: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 229: igraph_vector_int_push_back(&edges, tooff + vto);

line 239: igraph_vector_int_push_back(&edges, fromoff + vfrom);

line 240: igraph_vector_int_push_back(&edges, tooff + vto);

games/preference.c (16 calls)


line 285: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 286: igraph_vector_int_push_back(&edges, VECTOR(*v2)[to]);

line 294: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 295: igraph_vector_int_push_back(&edges, VECTOR(*v1)[to]);

line 304: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 305: igraph_vector_int_push_back(&edges, VECTOR(*v1)[to]);

line 311: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 312: igraph_vector_int_push_back(&edges, VECTOR(*v1)[to]);

line 318: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 319: igraph_vector_int_push_back(&edges, VECTOR(*v1)[to]);

line 574: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 575: igraph_vector_int_push_back(&edges, VECTOR(*v2)[to]);

line 581: igraph_vector_int_push_back(&edges, VECTOR(*v1)[from]);

line 582: igraph_vector_int_push_back(&edges, VECTOR(*v2)[to]);

isomorphism/isomorphism_misc.c (2 calls)


line 93: igraph_vector_int_push_back(&edges, from);

line 94: igraph_vector_int_push_back(&edges, to);

constructors/basic_constructors.c (1 call)


line 133: igraph_vector_int_push_back(&edges, num);

Note: 6 additional igraph_vector_push_back() calls (non-int variant) in random/random.c, games/citations.c, and properties/basic_properties.c are annotated with /* allocated */ or /* reserved */ comments — these are intentionally unchecked because capacity was pre-allocated.

Thank you for the feedback! Sorry again for the false positives.

6

Would you be able to re-run the python-igraph analysis with the latest main branch and share the results? A small number of issues are now fixed.

8

Hm, my post was flagged as spam and I cannot post the new report here. Do you have another form of contact I could use to send you the results?

10

If you try again, it should work. I marked it as “not spam”.

11

Thank you for restoring the post! But it still says I can’t post a link to the full report gist.

The full report is available at gist.github[.]com/devdanzin/38246591e423c703f575b8e816d8ab55.

Report complete. Please note that due to how the tool currently works, fixing issues frees agent context and attention, leading to discovery of more issues that weren’t caught before. Here’s a summary:

33 FIX, 24 CONSIDER, 7 POLICY from all 13 agents after deduplication.

Top findings (post-PR #879):

  1. sizeof(loc) heap buffer overflow — allocates pointer-size (8 bytes) instead of struct-size. One-character fix (sizeof(*loc)). Highest severity. FALSE POSITIVE.
  2. GRAPH_PROXY_METHOD unchecked PyTuple_New — 2-line macro fix affects 26 methods. Highest leverage.
  3. PyObject_CallObject removal in 3.15 — 4 calls, build-breaking. Must fix before 3.15 beta.
  4. PyFloat_AsDouble(o) wrong variable — should be PyFloat_AsDouble(result). Silent wrong results for non-float graph attributes.
  5. ~25 unchecked PyList_New/PyTuple_New — crash on OOM. Same bug class as PR #879 but in Python allocation APIs (not igraph’s calloc).
  6. BFSIter/DFSIter __new__() crash — uninitialized igraph containers destroyed on dealloc.
  7. Per-iteration ref leak in adjmatrix_get_index_row — extra Py_INCREF on the PyLong_FromLong path.
  8. Cascading leaks in rng_Python_set_generator — 8 PyLong objects leaked on error.
  9. strdup leak in eigen_which_t — leaked on 6 error returns.
  10. DRL options blanket PyErr_Clear — swallows all exceptions including MemoryError.

The report explicitly notes which findings from the original report were fixed by PR #879 and which remain.

Reproducer results:

  ┌─────┬──────────────────────────────────────┬───────────────────────┬─────────────────────────────────────────────────────────────────┐
  │  #  │               Finding                │        Status         │                            Evidence                             │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 26  │ EdgeSeq/VertexSeq __new__() segfault │ Reproduced            │ SEGV confirmed by ASan                                          │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 24  │ BFSIter/DFSIter __new__() UB         │ Reproduced (no crash) │ Dealloc on uninitialized containers, UB                         │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 25  │ Edge/Vertex __new__() crash          │ Reproduced            │ ValueError caught by partial guard                              │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 28  │ DRL options MemoryError swallowed    │ Reproduced            │ BadOptions __getattr__ raising MemoryError — silently swallowed │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 10  │ adjmatrix ref leak                   │ Reproduced            │ 4.8 bytes per get_adjacency() call                              │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 12  │ RNG set_generator leak               │ Reproduced            │ 44.9 bytes per set_random_number_generator() call               │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 5   │ convex_hull o1_float leak            │ Reproduced            │ 0.7 bytes per failed call with BadFloat                         │
  ├─────┼──────────────────────────────────────┼───────────────────────┼─────────────────────────────────────────────────────────────────┤
  │ 1   │ sizeof(loc) overflow                 │ FALSE POSITIVE        │ igraph_safelocale_t is a pointer typedef — sizes are equal      │
  └─────┴──────────────────────────────────────┴───────────────────────┴─────────────────────────────────────────────────────────────────┘
12

I’ll make a post about the work I’ve been doing with these toolkits in discuss.python.org. The draft is at https://gist.github[.]com/devdanzin/bbe7197dede8557a2c306ed1985d40e9, I’m open to all and any feedback if it interests you :slight_smile:

Daniel