Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

sequential_vertex_coloring out-of-bounds memory access

已关闭 适合新手
  • 哪里不对？
#627 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

@Becheler 已经在做这个了。

开始于 2026年10月7日。

评估

难度
2/5
预计耗时
1-3 小时
新手友好度
78/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
cpp
领域
backend

调研方向

从 sequential_vertex_coloring.hpp 和随附的 tests.cpp reproducer 开始。检查图经过筛选且未提供 order property map 时，默认的 order property map 是如何构建和使用的。在原始图和筛选后的图上都运行 reproducer；当针对筛选后图的调用完成且没有发生越界访问时，即为完成。

由索引模型根据 Issue 内容生成。

描述

The algorithm encoded in sequential_vertex_coloring.hpp accesses memory out of bounds when called with (i) a filtered graph, i.e., one for which num_vertices(g) > distance(vertices(g).first,vertices(g).second), and (ii) no order property map. This is because, for a filtered graph, the order property map constructed by the algorithm is too small. The algorithm documents the order property map to have the following property:

 A mapping from integers in the range [0, num_vertices(g)) to the vertices of the graph.

However, it is constructed from vertices(g), not num_vertices(g). For filtered graphs, the former range may be smaller than the latter, yet the algorithm itself accesses all the vertices returned by num_vertices(g), i.e., in the range referred to above. Therefore, out-of-bounds memory access is possible.

See below for a reproducer and a patch that works for me. Although I have tested this only on Boost v1.86.0, the file in question is unchanged for seven years and contains the same code.

Before filing
  • [ x] I searched the existing issues and did not find a duplicate.
  • [x ] I have reproduced the bug against the develop branch or the latest Boost release.
  • [x ] I have a minimal reproducer (or I will paste my full failing code below).
Boost version

1.86.0

Compiler family
  • GCC / g++
  • [ x] Clang / clang++
  • MSVC (Visual Studio)
  • Intel / oneAPI
  • Other (specify below)

Exact compiler version:

Apple clang version 16.0.0 (clang-1600.0.26.4)

Standard library
  • libstdc++
  • libc++
  • MSVC STL
  • Other (specify below)
Operating system
  • Linux
  • [ x] macOS
  • Windows
  • Other (specify below)
Kind of component affected
  • Graph data structure (e.g. adjacency_list, adjacency_matrix)
  • [ x] Algorithm (e.g. dijkstra_shortest_paths, breadth_first_search)
  • Property map
  • I/O or file-format reader (e.g. read_graphml, read_graphviz)
  • Visitor / event hooks
  • Other (specify below)

Exact name of the affected component:

sequential_vertex_coloring

Steps to reproduce

(i) create a filtered graph (g) that reduces the number of vertices
(ii) call sequential_vertex_coloring(g,color_map), i.e., without an order property map

See the attached reproducer, which colors both the original and filtered graphs to demonstrate the problem only with the latter.

Expected behavior

The algorithm should complete.

Actual behavior

Segmentation fault, i.e., signal 11.

Are you willing to help?
  • I'd like to submit a fix as a pull request.
  • I can help diagnose or test a candidate fix.
  • [ x] I'm only reporting the issue.

I am happy to help test as needed, but this report should be entirely self-contained with a reproducer and a patch (see below).

tests.cpp

sequential_vertex_coloring.hpp.patch

主要语言
C++
星标
397
派生
246
平均合并
1 天 15 小时
30 天内合并 PR
31

环境准备

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

boostorg/graph 的其他 Issue

查看 boostorg/graph 的全部 Issue

相似的 Issue

更多 C++ Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。