Abstract. We define the signature packing number of a signed graph [Formula: see text], denoted [Formula: see text], to be the maximum number of signatures [Formula: see text] such that each [Formula: see text] is switching-equivalent to [Formula: see text] and the sets [Formula: see text], negative edges of [Formula: see text], are pairwise disjoint. In this work, first in connection to recent developments on the theory of homomorphisms of signed graphs, we prove that for a signed graph [Formula: see text], [Formula: see text] if and only if [Formula: see text] admits a homomorphism to [Formula: see text], where [Formula: see text] is obtained from [Formula: see text] by adding a positive loop to every vertex. Noting that [Formula: see text] , signed projective cube of dimension [Formula: see text] , is the signed (Cayley) graph built on [Formula: see text] where two binary strings at Hamming distance 1 are adjacent by a positive edge and those at Hamming distance [Formula: see text] are adjacent by a negative edge. In other words, [Formula: see text] is built from the hypercube of dimension [Formula: see text] by considering all its edges as positive edges and adding a negative edge for each pair of antipodal vertices. In special cases we have the following: I. A simple graph [Formula: see text] is 4-colorable if and only if [Formula: see text]. II. A signed bipartite graph [Formula: see text] maps to [Formula: see text] if and only if [Formula: see text] noting that [Formula: see text] is the same as [Formula: see text], that is, a signed graph on [Formula: see text] where the set of negative edges forms a perfect matching. On restriction to planar graphs, I is then a restatement of the 4-color theorem, and II is implied by an unpublished work of Guenin. After further development of this theory of packing in signed graphs, we give an independent proof of II, which works on the larger class of [Formula: see text]-minor-free graphs. More precisely, we prove the following theorem. Theorem. If [Formula: see text] is a [Formula: see text] -minor-free bipartite simple graph, then for any signature [Formula: see text] we have [Formula: see text]. The statement is shown to be strictly stronger than the 4-color theorem and is proved assuming it. Furthermore, we show that I cannot be extended to the class of all signed planar simple graphs. Further developments, including algorithmic implications, are considered.

Greybox fuzzing has been widely used in vulnerabilities detection. Most greybox fuzzing tools are coverage-based, which usually use basic block transition to gain code coverage and focus on improving it to trigger more bugs. However, only increasing code coverage is insufficient to find some heap-based vulnerabilities such as use-after-free (UAF) and double-free (DF). This is because, to trigger these vulnerabilities, one needs not only to cover more code, but also to execute special heap operations to satisfy a particular temporal constraint (i.e., allocating heap memory, free memory, and accessing the heap memory). In this paper, we propose an approach, namely MDFuzz, to detect heap-based vulnerabilities adopting multi-level directed greybox fuzzing. The key idea is identifying different targets to guide the fuzzing process to cover specific heap operations without wasting resources exploring unrelated program components. We first perform a static analysis to automatically recognize three critical targets related to heap operations and then calculate each basic block's distance to the targets. Moreover, we propose a probability-based multi-level seed queue and a novel seed selection strategy to augment the guidance of directed fuzzing. To evaluate MDFuzz, we have performed an evaluation on 7 real-world applications. The experimental results demonstrate that MDFuzz significantly outperforms the state-of-the-art fuzzers, including AFL, AFLFast and VUzzer, in terms of the time consumed to discover heap-based vulnerabilities. Moreover, MD-Fuzz found 4 previously unknown vulnerabilities in real-world programs.