Talos Vulnerability Report

SUMMARY

An improper array index validation vulnerability exists in the GraphPlanar::Write functionality of Diagon v1.0.139. A specially crafted markdown file can lead to memory corruption. A victim would need to open a malicious file to trigger this vulnerability.

CONFIRMED VULNERABLE VERSIONS

The versions below were either tested or verified to be vulnerable by Talos or confirmed to be vulnerable by the vendor.

Diagon v1.0.139

PRODUCT URLS

Diagon - https://github.com/ArthurSonzogni/Diagon

CVSSv3 SCORE

5.3 - CVSS:3.1/AV:L/AC:L/PR:N/UI:R/S:U/C:L/I:L/A:L

CWE

CWE-119 - Improper Restriction of Operations within the Bounds of a Memory Buffer

DETAILS

Diagon is an interpreter that translates markdown into several formats: latex, planar graph, table, tree and many others.

The Diagon interpreter translates from a representation of a graph to a planar graph. For instance, the input could looks like this:

A--B--C--D--E--F--D--C

And the planar graph would result in:

      ┌─┐
      │A│
      └┬┘
      ┌┴┐
      │B│
      └┬┘
┌─────┐│
│  D  ││
└┬─┬─┬┘│
 │ │┌┴┐│
 │ ││E││
 │ │└┬┘│
 │┌┴─┴┐│
 ││ F ││
 │└───┘│
┌┴─────┴─┐
│   C    │
└────────┘

The input will be parsed and eventually reach the GraphPlanar::Write() function:

void GraphPlanar::Write() {
  ComputeArrowStyle();

  if (id_to_name.size() <= 2) {
    return;
  }

  int num_vertices = id_to_name.size();

  // Create a graph.
  Graph graph(num_vertices);
  for (auto& it : vertex)
    add_edge(it.from, it.to, graph);
  InitializeEdgeIndex(graph);

  // Make it connected.
  boost::make_connected(graph);                                                                         [1]
  InitializeEdgeIndex(graph);

  // Make it biconnected.
  Embedding embedding;
  bool is_planar = ComputePlanarEmbedding(graph, embedding);
  if (!is_planar) {
    output_ = "Graph is not planar.\n";
    return;
  }

  boost::make_biconnected_planar(graph, embedding.data());                                              [2]
  InitializeEdgeIndex(graph);
  Graph biconnected_graph(graph);

  ComputePlanarEmbedding(graph, embedding);
  boost::make_maximal_planar(graph, embedding.data());                                                  [3]
  InitializeEdgeIndex(graph);

  // Find a canonical ordering.
  ComputePlanarEmbedding(graph, embedding);
  std::vector<boost::graph_traits<Graph>::vertex_descriptor> ordering;
  boost::planar_canonical_ordering(graph, embedding.data(),
                                   std::back_inserter(ordering));                                       [4]

  std::vector<size_t> inverse_ordering(num_vertices);                                                   [5]
  for (int i = 0; i < inverse_ordering.size(); ++i) {
    inverse_ordering[ordering[i]] = i;                                                                  [6]
  }
  [...]
}

This function, until the code at [3], will manipulate the graph representation of the input to satisfy the pre-requisites of the planar_canonical_ordering function at [4]. Indeed, to call the planar_canonical_ordering at [4], the graph must be maximal planar; that is, calculated at [3]. Before calling the make_maximal_planar at [3] the graph must be biconnected. To make the graph biconnected, the function make_biconnected_planar, at [2], is called. The last dependency is that the graph must be connected, which is satisfied using make_connected called at [1].

The Graph type is defined as follows:

using Graph = boost::adjacency_list<boost::vecS,
                            boost::vecS,
                            boost::undirectedS,
                            boost::property<boost::vertex_index_t, int>,
                            boost::property<boost::edge_index_t, int>>;

The first template parameter is used to specify how to store the edges. In this case, the boost::vecS will store the edges in a std::vector. This configuration will allow parallel edges. For instance, in the example bellow, we have the edge (C,D) but also (D,E).

Using the boost::vecS, allegedly, will break some assumption of the called function. For instance, it could create a graph that is not biconnected at [2]. This can lead to an out-of-bounds read and write. In the POC shown below, after calling the planar_canonical_ordering function at [4] the ordering will have a number of elements lower than the num_vertices variable that represent the number of vertices in the graph. Because inverse_ordering, at [5] , is created based on the actual number of vertices, the inverse_ordering buffer and the ordering one will mismatch in sizes. This would cause, at [6], an out-of-bounds read and write, possibly resulting in a memory corruption.

Exploit Proof of Concept

Following the content of the POC used:

$ cat POC.md
A--B--C--D--E--F--D--C

If we run Diagon compile with ASAN with the POC:

$ diagon GraphPlanar < POC.md
AddressSanitizer:DEADLYSIGNAL
=================================================================
==3943598==ERROR: AddressSanitizer: SEGV on unknown address (pc 0x0000006952ef bp 0x7ffddd10d730 sp 0x7ffddd10c7e0 T0)
==3943598==The signal is caused by a READ memory access.
==3943598==Hint: this fault was caused by a dereference of a high value address (see register values below).  Dissassemble the provided pc to learn which register was used.
    #0 0x6952ef in GraphPlanar::Write() /home/vagrant/Diagon/src/translator/graph_planar/GraphPlanar.cpp:342:35
    #1 0x693085 in GraphPlanar::Translate(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /home/vagrant/Diagon/src/translator/graph_planar/GraphPlanar.cpp:194:3
    #2 0x4fbd0e in (anonymous namespace)::Translate(Translator*, int, char const**) /home/vagrant/Diagon/src/main.cpp:277:36
    #3 0x4f97e7 in main /home/vagrant/Diagon/src/main.cpp:326:12
    #4 0x7fe4a9895d09 in __libc_start_main csu/../csu/libc-start.c:308:16
    #5 0x44ca69 in _start (/home/vagrant/Diagon/results/ordering_graphplanar_write_error/diagon_unfixed+0x44ca69)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /home/vagrant/Diagon/src/translator/graph_planar/GraphPlanar.cpp:342:35 in GraphPlanar::Write()
==3943598==ABORTING

We can see that a segmentation fault occured. The GraphPlanar.cpp:342 line corresponds to the code at [6]

VENDOR RESPONSE

The maintainer has provided a patch at: https://github.com/ArthurSonzogni/Diagon/releases/tag/v1.1.158

TIMELINE

2023-05-03 - Vendor Disclosure
2023-05-08 - Vendor Patch Release
2023-07-05 - Public Release