Misleading bidirectional detection

[serge-sans-paille]

Summary

This patch implements detection of incomplete bidirectional sequence withing comments and string literals within clang-tidy.

It detects the bidi part of https://www.trojansource.codes/trojan-source.pdf

[rsmith]

Nits and a suggested approach for invalid code sequences that's probably important to handle better. Please fix the clang-tidy findings too. Otherwise, LGTM.

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

39

Nit: please use // comments per our normal coding style.

50

61–63

Can we scan forward looking for the next non-continuation byte? (Skip while c & 0b1100_0000 == 0b1000_0000)

75

[carlosgalvezp]

Nice addition! Please add this check to the documentation (list of available checks + individual page with the documentation for this check), plus mention in the clang-tidy release notes. The same applies to the other related patches.

[carlosgalvezp]

clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp

61

Nit: please keep alphabetical order in the list of jobs.

[MaskRay]

Context not available.

If you don't use arc diff 'HEAD^' to upload a Diff, please use -U99999 https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

16

See https://llvm.org/docs/CodingStandards.html#use-namespace-qualifiers-to-implement-previously-declared-functions

[MaskRay]

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

20

functionName

20

clang-format bool HonorLineBreaks=true

21

48

52

no brace

99

delete blank line

clang-tools-extra/test/clang-tidy/check_clang_tidy.py

85 ↗

(On Diff #383745)

Prefer single quotes

[MaskRay]

clang-tools-extra/test/clang-tidy/checkers/misc-misleading-bidirectional.cpp

1

The test misses many interesting cases.

[serge-sans-paille]

• recover from failed utf8 decoding
• doc and release note updated
• clang-formatting
• more examples / testing

[rsmith]

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

60

Is there a guarantee that convertUTF8Sequence doesn't update CurPtr on error? I'm concerned we might increment *past* the end in the case where CurPtr points to the end, below, which would at least formally be UB.

[serge-sans-paille]

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

60

According to the doc "If the conversion succeeds, this pointer will be updated to point to the byte just past the end of the converted sequence". My understanding of the implementation confirms that statements, and it's used in a similar manner in clang Lexer.

61–63

I'm not quite sure. There's a risk we end up starting over from the second part of a unicode character, and that could mess up with the decoding. I'll investigate how it's done in other libraries.

[carlosgalvezp]

clang-tools-extra/docs/ReleaseNotes.rst

137

Nit: Inspects

[serge-sans-paille]

Rebase on main branch

[serge-sans-paille]

Patch rebased on main, all comments addressed. Looks good?

[serge-sans-paille]

Nits

[serge-sans-paille]

Gentle ping @MaskRay and/or @rsmith

[MaskRay]

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

50

/*next line=*/0x85 is more common

67

69

More common style is A = A ? A - 1 : 0; which avoids unsigned wraparound.

That said, if the state is currently 0, should an attempt to decrease it be reported as an error as well?

71

ditto

129

If you using MisleadingBidirectionalCheck (or clang::tidy::misc), then you can use

void MisleadingBidirectionalCheck::registerMatchers

clang-tools-extra/test/clang-tidy/checkers/misc-misleading-bidirectional.cpp

6

[[@LINE-1]] is a deprecated FileCheck feature.

Use [[#@LINE-1]]

[upsuper]

I'm not familiar with LLVM / Clang codebase. I was asked by @MaskRay to help review the bidi-related part of this patch.

Generally I believe the algorithm here is too naive that it produces both false positives and false negatives. I'm not sure how important those edge cases are considered, but anyway... detailed comments below:

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

49–50

UAX 14 is probably not the right document to look here.

According to UAX 9 step L1, the embedding level is reset to the paragraph embedding level when hitting segment separator and paragraph separator, which are defined in table 4 as type B and S, and in UCD DerivedBidiClass.txt you can see type B includes U+000A, U+000D, U+001C..001E, U+0085, U+2029, and type S includes U+0009, U+000B, and U+001F.

You have U+000C and U+2028 here which are counted as type WS which doesn't affect embedding level, so you may be resetting the counter prematurely. And you may want to reset the counter for all other characters above.

65–73

The bidi algorithm is more complicated than having two simple counters. Basically, a PDF cancels a override / embedding character only when they match, and PDI cancels all override / embedding between it and its matching isolate character.

I was thinking whether the counters would be enough in the sense that we may accept some false positive for edge cases but definitely no false negative. But I'm convinced it's not the case. As an example, a sequence of RLO LRI PDF PDI will yield no embedding and no isolate in this counting model, but the PDF here actually has no effect, as shown in step X7, if it does not match an embedding initiator, it is ignored, so this is effectively leaving a dangling RLO.

[serge-sans-paille]

Update bidi algorithm

[serge-sans-paille]

@upsuper I've not added extra test cases yet, but does it looks it's heading in the right direction?

[serge-sans-paille]

Fix some parts of the bidi algorithm, and add extra test cases

[upsuper]

I think the core algorithm looks correct now. I'll leave the code review to LLVM reviewers. Thanks.

[serge-sans-paille]

rebased on main branch

[serge-sans-paille]

Thanks @upsuper!

[aaron.ballman]

Has this been tested against any large code bases that use bidirectional characters to see what the false positive rate is? Also, have you seen the latest Unicode guidance on this topic: https://unicode.org/L2/L2022/22007-avoiding-spoof.pdf to make sure we're following along?

[serge-sans-paille]

@aaron.ballman unfortunately I don't know any of those. If I recall correctly we found no software in the RedHat collection actually using those control characters :-/
My understanding is that we are inline with the document you mention, except the fact that 1. We don't allow LRM character in plain text and 2. we do not check if a string / comment sequence ends in RTL state, but that actually requires another algorithm :-/

[serge-sans-paille]

Note that if there's a consensus on it, I can implement LRM character support.

[serge-sans-paille]

rebased

[serge-sans-paille]

@MaskRay any blocker on that new version now that it recieved a green light from @upsuper?

[upsuper]

I'd like to clarify that what I think is correct now is the algorithm to detect unclosed explicit formatting scopes in a given string.

I haven't been following very closely with the whole spoofing issue, so I can't say that there is no other ways to construct a spoof that this algorithm is not designed to detect.

As you have found, RLM, and ALM can be used to confuse code reader, but they are not much different than a string with other strong RTL characters inside, and I don't quite see how that can be linted without hurting potentially legitimate code. Maybe if the compiler supports treating LRM as whitespace (I'm not sure whether Clang does), a lint may be added to ask wrapping any string with outermost strong characters being RTL in the form of {LRM}"string"{LRM} so that the RTL characters don't affect outside. Other than that, I don't think there is anyway to lint against such a confusion.

[serge-sans-paille]

In D112913#3233699, @upsuper wrote:

I'd like to clarify that what I think is correct now is the algorithm to detect unclosed explicit formatting scopes in a given string.

Thanks for confirming. This check only detects unterminated bidi sequence within comments and string literals. Its scope limits to that aspect.

I haven't been following very closely with the whole spoofing issue, so I can't say that there is no other ways to construct a spoof that this algorithm is not designed to detect.

Agreed. FYI we already have a check for RTL characters ending identfiers, and a pending one for confusable identifiers

As you have found, RLM, and ALM can be used to confuse code reader, but they are not much different than a string with other strong RTL characters inside, and I don't quite see how that can be linted without hurting potentially legitimate code. Maybe if the compiler supports treating LRM as whitespace (I'm not sure whether Clang does), a lint may be added to ask wrapping any string with outermost strong characters being RTL in the form of {LRM}"string"{LRM} so that the RTL characters don't affect outside. Other than that, I don't think there is anyway to lint against such a confusion.

I agree that allowing LRM is a good step forward, and that's part of the official recommendation, but orthogonal to that review.

[MaskRay]

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

17

Consider using clang::tidy::misc::MisleadingBidirectionalCheck to avoid specifying the long name repeatedly.

44

i is unused

49

You may save the conditions to two booleans to avoid repeated BidiContexts.clear();

67

A sentence should end with a period.

clang-tools-extra/clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_library(clangTidyMiscModule
   DefinitionsInHeadersCheck.cpp
   MiscTidyModule.cpp
+  MisleadingBidirectional.cpp
   MisleadingIdentifier.cpp
   MisplacedConstCheck.cpp
   NewDeleteOverloadsCheck.cpp
   NoRecursionCheck.cpp
   NonCopyableObjects.cpp
   NonPrivateMemberVariablesInClassesCheck.cpp
   RedundantExpressionCheck.cpp
   StaticAssertCheck.cpp

clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp

 //===--- MiscTidyModule.cpp - clang-tidy ----------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "DefinitionsInHeadersCheck.h"
+#include "MisleadingBidirectional.h"
 #include "MisleadingIdentifier.h"
 #include "MisplacedConstCheck.h"
 #include "NewDeleteOverloadsCheck.h"
 #include "NoRecursionCheck.h"
 #include "NonCopyableObjects.h"
 #include "NonPrivateMemberVariablesInClassesCheck.h"
 #include "RedundantExpressionCheck.h"
 #include "StaticAssertCheck.h"
 #include "ThrowByValueCatchByReferenceCheck.h"
 #include "UnconventionalAssignOperatorCheck.h"
 #include "UniqueptrResetReleaseCheck.h"
 #include "UnusedAliasDeclsCheck.h"
 #include "UnusedParametersCheck.h"
 #include "UnusedUsingDeclsCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace misc {
 
 class MiscModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<DefinitionsInHeadersCheck>(
         "misc-definitions-in-headers");
+    CheckFactories.registerCheck<MisleadingBidirectionalCheck>(
+        "misc-misleading-bidirectional");
     CheckFactories.registerCheck<MisleadingIdentifierCheck>(
         "misc-misleading-identifier");
     CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
     CheckFactories.registerCheck<NewDeleteOverloadsCheck>(
         "misc-new-delete-overloads");
     CheckFactories.registerCheck<NoRecursionCheck>("misc-no-recursion");
     CheckFactories.registerCheck<NonCopyableObjectsCheck>(
         "misc-non-copyable-objects");
     CheckFactories.registerCheck<NonPrivateMemberVariablesInClassesCheck>(
         "misc-non-private-member-variables-in-classes");
     CheckFactories.registerCheck<RedundantExpressionCheck>(
         "misc-redundant-expression");
     CheckFactories.registerCheck<StaticAssertCheck>("misc-static-assert");
     CheckFactories.registerCheck<ThrowByValueCatchByReferenceCheck>(
         "misc-throw-by-value-catch-by-reference");
     CheckFactories.registerCheck<UnconventionalAssignOperatorCheck>(
         "misc-unconventional-assign-operator");
     CheckFactories.registerCheck<UniqueptrResetReleaseCheck>(
         "misc-uniqueptr-reset-release");
     CheckFactories.registerCheck<UnusedAliasDeclsCheck>(
         "misc-unused-alias-decls");
     CheckFactories.registerCheck<UnusedParametersCheck>(
         "misc-unused-parameters");
     CheckFactories.registerCheck<UnusedUsingDeclsCheck>(
         "misc-unused-using-decls");
   }
 };
 
 } // namespace misc
 

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.h

+//===--- MisleadingBidirectionalCheck.h - clang-tidy ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_MISLEADINGBIDIRECTIONALCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_MISLEADINGBIDIRECTIONALCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+class MisleadingBidirectionalCheck : public ClangTidyCheck {
+public:
+  MisleadingBidirectionalCheck(StringRef Name, ClangTidyContext *Context);
+  ~MisleadingBidirectionalCheck();
+
+  void registerPPCallbacks(const SourceManager &SM, Preprocessor *PP,
+                           Preprocessor *ModuleExpanderPP) override;
+
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  class MisleadingBidirectionalHandler;
+  std::unique_ptr<MisleadingBidirectionalHandler> Handler;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_MISLEADINGBIDIRECTIONALCHECK_H

clang-tools-extra/clang-tidy/misc/MisleadingBidirectional.cpp

+//===--- MisleadingBidirectional.cpp - clang-tidy -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "MisleadingBidirectional.h"
+
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Lex/Preprocessor.h"
+#include "llvm/Support/ConvertUTF.h"
+
+using namespace clang;
+using namespace clang::tidy::misc;
+
+static bool containsMisleadingBidi(StringRef Buffer,
+                                   bool HonorLineBreaks = true) {
+  const char *CurPtr = Buffer.begin();
+
+  enum BidiChar {
+    PS = 0x2029,
+    RLO = 0x202E,
+    RLE = 0x202B,
+    LRO = 0x202D,
+    LRE = 0x202A,
+    PDF = 0x202C,
+    RLI = 0x2067,
+    LRI = 0x2066,
+    FSI = 0x2068,
+    PDI = 0x2069
+  };
+
+  SmallVector<BidiChar> BidiContexts;
+
+  // Scan each character while maintaining a stack of opened bidi context.
+  // RLO/RLE/LRO/LRE all are closed by PDF while RLI LRI and FSI are closed by
+  // PDI. New lines reset the context count. Extra PDF / PDI are ignored.
+  //
+  // Warn if we end up with an unclosed context.
+  while (CurPtr < Buffer.end()) {
+    unsigned char C = *CurPtr;
+    if (isASCII(C)) {
+      ++CurPtr;
+      bool IsParagrapSep =
+          (C == 0xA || C == 0xD || (0x1C <= C && C <= 0x1E) || C == 0x85);
+      bool IsSegmentSep = (C == 0x9 || C == 0xB || C == 0x1F);
+      if (IsParagrapSep || IsSegmentSep)
+        BidiContexts.clear();
+      continue;
+    }
+    llvm::UTF32 CodePoint;
+    llvm::ConversionResult Result = llvm::convertUTF8Sequence(
+        (const llvm::UTF8 **)&CurPtr, (const llvm::UTF8 *)Buffer.end(),
+        &CodePoint, llvm::strictConversion);
+
+    // If conversion fails, utf-8 is designed so that we can just try next char.
+    if (Result != llvm::conversionOK) {
+      ++CurPtr;
+      continue;
+    }
+
+    // Open a PDF context.
+    if (CodePoint == RLO || CodePoint == RLE || CodePoint == LRO ||
+        CodePoint == LRE)
+      BidiContexts.push_back(PDF);
+    // Close PDF Context.
+    else if (CodePoint == PDF) {
+      if (!BidiContexts.empty() && BidiContexts.back() == PDF)
+        BidiContexts.pop_back();
+    }
+    // Open a PDI Context.
+    else if (CodePoint == RLI || CodePoint == LRI || CodePoint == FSI)
+      BidiContexts.push_back(PDI);
+    // Close a PDI Context.
+    else if (CodePoint == PDI) {
+      auto R = std::find(BidiContexts.rbegin(), BidiContexts.rend(), PDI);
+      if (R != BidiContexts.rend())
+        BidiContexts.resize(BidiContexts.rend() - R - 1);
+    }
+    // Line break or equivalent
+    else if (CodePoint == PS)
+      BidiContexts.clear();
+  }
+  return !BidiContexts.empty();
+}
+
+class MisleadingBidirectionalCheck::MisleadingBidirectionalHandler
+    : public CommentHandler {
+public:
+  MisleadingBidirectionalHandler(MisleadingBidirectionalCheck &Check,
+                                 llvm::Optional<std::string> User)
+      : Check(Check) {}
+
+  bool HandleComment(Preprocessor &PP, SourceRange Range) override {
+    // FIXME: check that we are in a /* */ comment
+    StringRef Text =
+        Lexer::getSourceText(CharSourceRange::getCharRange(Range),
+                             PP.getSourceManager(), PP.getLangOpts());
+
+    if (containsMisleadingBidi(Text, true))
+      Check.diag(
+          Range.getBegin(),
+          "comment contains misleading bidirectional Unicode characters");
+    return false;
+  }
+
+private:
+  MisleadingBidirectionalCheck &Check;
+};
+
+MisleadingBidirectionalCheck::MisleadingBidirectionalCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      Handler(std::make_unique<MisleadingBidirectionalHandler>(
+          *this, Context->getOptions().User)) {}
+
+MisleadingBidirectionalCheck::~MisleadingBidirectionalCheck() = default;
+
+void MisleadingBidirectionalCheck::registerPPCallbacks(
+    const SourceManager &SM, Preprocessor *PP, Preprocessor *ModuleExpanderPP) {
+  PP->addCommentHandler(Handler.get());
+}
+
+void MisleadingBidirectionalCheck::check(
+    const ast_matchers::MatchFinder::MatchResult &Result) {
+  if (const auto *SL = Result.Nodes.getNodeAs<StringLiteral>("strlit")) {
+    StringRef Literal = SL->getBytes();
+    if (containsMisleadingBidi(Literal, false))
+      diag(SL->getBeginLoc(), "string literal contains misleading "
+                              "bidirectional Unicode characters");
+  }
+}
+
+void MisleadingBidirectionalCheck::registerMatchers(
+    ast_matchers::MatchFinder *Finder) {
+  Finder->addMatcher(ast_matchers::stringLiteral().bind("strlit"), this);
+}

clang-tools-extra/docs/ReleaseNotes.rst

- New :doc:`readability-container-data-pointer
   element at index 0 in a container.
 
 - New :doc:`readability-identifier-length
   <clang-tidy/checks/readability-identifier-length>` check.
 
   Reports identifiers whose names are too short. Currently checks local
   variables and function parameters only.
 
+- New :doc:`misc-misleading-bidirectional <clang-tidy/checks/misc-misleading-bidirectional>` check.
+
+  Inspects string literal and comments for unterminated bidirectional Unicode
+  characters.
 
 New check aliases
 ^^^^^^^^^^^^^^^^^
 
 - New alias :doc:`cert-err33-c
   <clang-tidy/checks/cert-err33-c>` to
   :doc:`bugprone-unused-return-value
   <clang-tidy/checks/bugprone-unused-return-value>` was added.
 
 - New alias :doc:`cert-exp42-c
   <clang-tidy/checks/cert-exp42-c>` to
   :doc:`bugprone-suspicious-memory-comparison

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. csv-table::
    `llvm-namespace-comment <llvm-namespace-comment.html>`_,
    `llvm-prefer-isa-or-dyn-cast-in-conditionals <llvm-prefer-isa-or-dyn-cast-in-conditionals.html>`_, "Yes"
    `llvm-prefer-register-over-unsigned <llvm-prefer-register-over-unsigned.html>`_, "Yes"
    `llvm-twine-local <llvm-twine-local.html>`_, "Yes"
    `llvmlibc-callee-namespace <llvmlibc-callee-namespace.html>`_,
    `llvmlibc-implementation-in-namespace <llvmlibc-implementation-in-namespace.html>`_,
    `llvmlibc-restrict-system-libc-headers <llvmlibc-restrict-system-libc-headers.html>`_, "Yes"
    `misc-definitions-in-headers <misc-definitions-in-headers.html>`_, "Yes"
-   `misc-misleading-identifier <misc-misleading-identifier.html>`_,
+   `misc-misleading-bidirectional <misc-misleading-bidirectional.html>`_,
+   `misc-misleading-identifier <misc-mileading-identifier.html>`_,
    `misc-misplaced-const <misc-misplaced-const.html>`_,
    `misc-new-delete-overloads <misc-new-delete-overloads.html>`_,
    `misc-no-recursion <misc-no-recursion.html>`_,
    `misc-non-copyable-objects <misc-non-copyable-objects.html>`_,
    `misc-non-private-member-variables-in-classes <misc-non-private-member-variables-in-classes.html>`_,
    `misc-redundant-expression <misc-redundant-expression.html>`_, "Yes"
    `misc-static-assert <misc-static-assert.html>`_, "Yes"
    `misc-throw-by-value-catch-by-reference <misc-throw-by-value-catch-by-reference.html>`_,

clang-tools-extra/docs/clang-tidy/checks/misc-misleading-bidirectional.rst

+.. title:: clang-tidy - misc-misleading-bidirectional
+
+misc-misleading-bidirectional
+=============================
+
+Warn about unterminated bidirectional unicode sequence, detecting potential attack
+as described in the `Trojan Source <https://www.trojansource.codes>`_ attack.
+
+Example:
+
+.. code-block:: c++
+
+    #include <iostream>
+
+    int main() {
+        bool isAdmin = false;
+        /*‮ } ⁦if (isAdmin)⁩ ⁦ begin admins only */
+            std::cout << "You are an admin.\n";
+        /* end admins only ‮ { ⁦*/
+        return 0;
+    }