原文链接：

CTR57-CPP. Provide a valid ordering predicate

https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR57-CPP.+Provide+a+valid+ordering+predicate

关联容器在他们的键比较谓词上设置了严格的弱排序要求 [ISO/IEC 14882-2014]。一个严格的弱排序具有以下特性：

  • 对于所有的 x: x < x == false (非自反性)
  • 对于所有的 x, y: 如果 x < y 那么!(y < x) (不对称性)
  • 对于所有的 x, y, z: 如果 x < y && y < z 那么 x < z (传递性)

提供无效排序的谓词给对关联容器 (e.g., sets, maps, multisets, and multimaps)，或者作为排序算法的比较准测，会导致奇怪的行为或者无线循环 [Meyers 01]。当关联容器或者通用标准模板库算法需要一个排序谓词时，谓词必须满足严格的弱排序要求。

Associative containers place a strict weak ordering requirement on their key comparison predicates [ISO/IEC 14882-2014]. A strict weak ordering has the following properties:

  • for all x: x < x == false (irreflexivity)
  • for all x, y: if x < y then !(y < x) (asymmetry)
  • for all x, y, z: if x < y && y < zthenx < z (transitivity)

Providing an invalid ordering predicate for an associative container (e.g., sets, maps, multisets, and multimaps), or as a comparison criterion with the sorting algorithms, can result in erratic behavior or infinite loops [Meyers 01]. When an ordering predicate is required for an associative container or a generic standard template library algorithm, the predicate must meet the requirements for inducing a strict weak ordering.

不合规的代码示例 Noncompliant Code Example

在这个不合规的代码示例中，通过使用不遵循严格弱排序要求的比较器来创建 std::set 对象。特别地，对于相等的值这不会返回 false。因此，遍历来自 std::set::equal_range 返回的结果将造成 unspecified behavior。

In this noncompliant code example, the std::set object is created with a comparator that does not adhere to the strict weak ordering requirement. Specifically, it fails to return false for equivalent values. As a result, the behavior of iterating over the results from std::set::equal_range results in unspecified behavior.

1
2
3
4
5
6
7
8
9
10
#include <functional>
#include <iostream>
#include <set>

void f() {
  std::set<int, std::less_equal<int>> s{5, 10, 20};
  for (auto r = s.equal_range(10); r.first != r.second; ++r.first) {
    std::cout << *r.first << std::endl;
  }
}

合规方案 Compliant Solution

这个合规方案使用 std::set 默认比较器替换提供的不合理的比较器。

This compliant solution uses the default comparator with std::set instead of providing an invalid one.

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <set>

void f() {
  std::set<int> s{5, 10, 20};
  for (auto r = s.equal_range(10); r.first != r.second; ++r.first) {
    std::cout << *r.first << std::endl;
  }
}

不合规的代码示例 Noncompliant Code Example

在这个不合规的代码示例中，被存储在 std::set 的对象有一个重载 operator< 的实现，允许对象通过 std::less 来比较。然而，比较运算没有提供严格的弱排序。特别地，两个 sets，x 和 y，值均为 1， 但是 j 的值不一样，会导致 comp(x, y) 和 comp(y, x) 均返回 false 的场景。不满足非对称要求。

In this noncompliant code example, the objects stored in the std::set have an overloaded operator< implementation, allowing the objects to be compared with std::less. However, the comparison operation does not provide a strict weak ordering. Specifically, two sets, x and y, whose i values are both 1, but have differing j values can result in a situation where comp(x, y) and comp(y, x) are both false, failing the asymmetry requirements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <set>

class S {
  int i, j;

public:
  S(int i, int j) : i(i), j(j) {}

  friend bool operator<(const S &lhs, const S &rhs) {
    return lhs.i < rhs.i && lhs.j < rhs.j;
  }

  friend std::ostream &operator<<(std::ostream &os, const S& o) {
    os << "i: " << o.i << ", j: " << o.j;
    return os;
  }
};

void f() {
  std::set<S> t{S(1, 1), S(1, 2), S(2, 1)};
  for (auto v : t) {
    std::cout << v << std::endl;
  }
}

合规方案 Compliant Solution

这个合规方案使用 std::tie() 来实现 operator< 严格的弱排序谓词。

This compliant solution uses std::tie() to properly implement the strict weak ordering operator< predicate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <set>
#include <tuple>

class S {
  int i, j;

public:
  S(int i, int j) : i(i), j(j) {}

  friend bool operator<(const S &lhs, const S &rhs) {
    return std::tie(lhs.i, lhs.j) < std::tie(rhs.i, rhs.j);
  }

  friend std::ostream &operator<<(std::ostream &os, const S& o) {
    os << "i: " << o.i << ", j: " << o.j;
    return os;
  }
};

void f() {
  std::set<S> t{S(1, 1), S(1, 2), S(2, 1)};
  for (auto v : t) {
    std::cout << v << std::endl;
  }
}

风险评估 Risk Assessment

使用一个无效排序规则会导致怪异的行为或无限循环。

Using an invalid ordering rule can lead to erratic behavior or infinite loops.

Rule Severity Likelihood Remediation Cost Priority Level
CTR57-CPP Low Probable High P2 L3

Automated Detection

Tool Version Checker Description
Parasoft C/C++test img CERT_CPP-CTR57-a For associative containers never use comparison function returning true for equal values

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

SEI CERT Oracle Coding Standard for Java MET10-J. Follow the general contract when implementing the compareTo() method

Bibliography

[ISO/IEC 14882-2014] Subclause 23.2.4, “Associative Containers”
[Meyers 2001] Item 21, “Always Have Comparison Functions Return False for Equal Values”
[Sutter 2004] Item 83, “Use a Checked STL Implementation”

SEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_left.pngSEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_up.pngSEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_right.png

备注，这里评论区提出了质疑，需要注意的。

Timmy Weerwag 发表：

The list of requirements at the top do not correctly specify a strict weak ordering. In fact, these only specify a strict partial ordering (note that asymetry is already implied by irreflexivity and transitivity). One also needs transitivity of incomparability.

The explanation for the second non-compliant example is also wrong. The relation is assymetric but fails the transitivity of incomparability. Consider P = (0, 2), Q = (2, 0) and R = (1, 3). Observe that P and Q are incomparable (neither P < Q nor Q < P), and Q and R are incomparable. However, P < R and hence, P and R are comparable.