String.h

#ifndef ROSE_BinaryAnalysis_String_H
#define ROSE_BinaryAnalysis_String_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
 
#include <Rose/BinaryAnalysis/MemoryMap.h>
#include <Rose/Diagnostics.h>
#include <Rose/Exception.h>
#include <Sawyer/CommandLine.h>
#include <Sawyer/Optional.h>
 
#include <boost/regex.hpp>
#include <unordered_set>
 
namespace Rose {
namespace BinaryAnalysis {
 
namespace Strings {
 
extern Sawyer::Message::Facility mlog;
 
typedef uint8_t                Octet;      
typedef std::vector<Octet>     Octets;     
typedef unsigned               CodeValue;  
typedef std::vector<CodeValue> CodeValues; 
typedef unsigned               CodePoint;  
typedef std::vector<CodePoint> CodePoints; 
class Exception: public Rose::Exception {
  public:
    Exception(const std::string& s) : Rose::Exception(s) {}
};
 
class ROSE_DLL_API FilterSpecification {
  public:
    enum class Type {
        EXACT_MATCH, 
        SUBSTRING,   
        REGEX        
    };
 
    enum class CaseSensitivity {
        SENSITIVE,  
        INSENSITIVE 
    };
 
  private:
    Type            type_;
    std::string     pattern_;
    CaseSensitivity caseSensitivity_;
 
  public:
    FilterSpecification(Type type, const std::string& pattern);
 
    FilterSpecification(const std::string& pattern, CaseSensitivity caseSensitivity);
 
    Type type() const { return type_; }
 
    const std::string& pattern() const { return pattern_; }
 
    CaseSensitivity caseSensitivity() const { return caseSensitivity_; }
 
    bool isCaseSensitive() const { return caseSensitivity_ == CaseSensitivity::SENSITIVE; }
};
 
class ROSE_DLL_API StringFilter {
  private:
    std::unordered_set<std::string> exactStrings_;
    std::unordered_set<std::string> substrings_;
    std::unordered_set<std::string> regexPatternsCaseSensitive_;
    std::unordered_set<std::string> regexPatternsCaseInsensitive_;
 
    mutable Sawyer::Optional<boost::regex> compiledRegexCaseSensitive_;
    mutable Sawyer::Optional<boost::regex> compiledRegexCaseInsensitive_;
    mutable bool                           regexNeedsUpdate_ = true;
 
    void updateRegex() const;
 
  public:
    void addFilter(const FilterSpecification& spec);
 
    bool match(const std::string& str) const;
};
 
enum State {
    FINAL_STATE      = -1, 
    COMPLETED_STATE  = -2, 
    INITIAL_STATE    = -3, 
    ERROR_STATE      = -4, 
    USER_DEFINED_0   = 0,  
    USER_DEFINED_1   = 1,  
    USER_DEFINED_2   = 2,  
    USER_DEFINED_MAX = 128 
};
 
bool isDone(State st);
 
void initDiagnostics();
 
class ROSE_DLL_API CharacterEncodingForm: public Sawyer::SharedObject {
  protected:
    State state_ = INITIAL_STATE;
 
  public:
    CharacterEncodingForm() {}
    virtual ~CharacterEncodingForm() {}
 
    typedef Sawyer::SharedPointer<CharacterEncodingForm> Ptr;
 
    virtual Ptr clone() const = 0;
 
    virtual std::string name() const = 0;
 
    virtual CodeValues encode(CodePoint) = 0;
 
    State state() const { return state_; }
 
    virtual State decode(CodeValue) = 0;
 
    virtual CodePoint consume() = 0;
 
    virtual void reset() = 0;
};
 
class ROSE_DLL_API NoopCharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
 
  protected:
    NoopCharacterEncodingForm() : cp_(0) {}
 
  public:
    typedef Sawyer::SharedPointer<NoopCharacterEncodingForm> Ptr;
 
    static Ptr                         instance() { return Ptr(new NoopCharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const override { return Ptr(new NoopCharacterEncodingForm(*this)); }
    virtual std::string                name() const override { return "no-op"; }
    virtual CodeValues                 encode(CodePoint cp) override;
    virtual State                      decode(CodeValue) override;
    virtual CodePoint                  consume() override;
    virtual void                       reset() override;
};
 
NoopCharacterEncodingForm::Ptr noopCharacterEncodingForm();
 
class ROSE_DLL_API Utf8CharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
 
  protected:
    Utf8CharacterEncodingForm() : cp_(0) {}
 
  public:
    typedef Sawyer::SharedPointer<Utf8CharacterEncodingForm> Ptr;
 
    static Ptr                         instance() { return Ptr(new Utf8CharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const override { return Ptr(new Utf8CharacterEncodingForm(*this)); }
    virtual std::string                name() const override { return "UTF-8"; }
    virtual CodeValues                 encode(CodePoint cp) override;
    virtual State                      decode(CodeValue) override;
    virtual CodePoint                  consume() override;
    virtual void                       reset() override;
};
 
Utf8CharacterEncodingForm::Ptr utf8CharacterEncodingForm();
 
class ROSE_DLL_API Utf16CharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
 
  protected:
    Utf16CharacterEncodingForm() : cp_(0) {}
 
  public:
    typedef Sawyer::SharedPointer<Utf16CharacterEncodingForm> Ptr;
 
    static Ptr                         instance() { return Ptr(new Utf16CharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const override { return Ptr(new Utf16CharacterEncodingForm(*this)); }
    virtual std::string                name() const override { return "UTF-16"; }
    virtual CodeValues                 encode(CodePoint cp) override;
    virtual State                      decode(CodeValue) override;
    virtual CodePoint                  consume() override;
    virtual void                       reset() override;
};
 
Utf16CharacterEncodingForm::Ptr utf16CharacterEncodingForm();
 
class ROSE_DLL_API CharacterEncodingScheme: public Sawyer::SharedObject {
  protected:
    State state_ = INITIAL_STATE;
 
  public:
    CharacterEncodingScheme() {}
    virtual ~CharacterEncodingScheme() {}
 
    typedef Sawyer::SharedPointer<CharacterEncodingScheme> Ptr;
 
    virtual Ptr clone() const = 0;
 
    virtual std::string name() const = 0;
 
    virtual Octets encode(CodeValue) = 0;
 
    State state() const { return state_; }
 
    virtual State decode(Octet) = 0;
 
    virtual CodeValue consume() = 0;
 
    virtual void reset() = 0;
};
 
class ROSE_DLL_API BasicCharacterEncodingScheme: public CharacterEncodingScheme {
    size_t                octetsPerValue_;
    ByteOrder::Endianness sex_;
    CodeValue             cv_;
 
  protected:
    BasicCharacterEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex) :
      octetsPerValue_(octetsPerValue), sex_(sex), cv_(0) {
        ASSERT_require(1 == octetsPerValue || sex != ByteOrder::ORDER_UNSPECIFIED);
        ASSERT_require(octetsPerValue <= sizeof(CodeValue));
    }
 
  public:
    static Ptr instance(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED) {
        return Ptr(new BasicCharacterEncodingScheme(octetsPerValue, sex));
    }
    virtual Ptr         clone() const override { return Ptr(new BasicCharacterEncodingScheme(*this)); }
    virtual std::string name() const override;
    virtual Octets      encode(CodeValue) override;
    virtual State       decode(Octet) override;
    virtual CodeValue   consume() override;
    virtual void        reset() override;
};
 
BasicCharacterEncodingScheme::Ptr
basicCharacterEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);
 
class ROSE_DLL_API LengthEncodingScheme: public Sawyer::SharedObject {
  protected:
    State state_ = INITIAL_STATE;
 
  public:
    LengthEncodingScheme() {}
    virtual ~LengthEncodingScheme() {}
 
    typedef Sawyer::SharedPointer<LengthEncodingScheme> Ptr;
 
    virtual Ptr clone() const = 0;
 
    virtual std::string name() const = 0;
 
    virtual Octets encode(size_t) = 0;
 
    State state() const { return state_; }
 
    virtual State decode(Octet) = 0;
 
    virtual size_t consume() = 0;
 
    virtual void reset() = 0;
};
 
class ROSE_DLL_API BasicLengthEncodingScheme: public LengthEncodingScheme {
    size_t                octetsPerValue_;
    ByteOrder::Endianness sex_;
    size_t                length_;
 
  protected:
    BasicLengthEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex) :
      octetsPerValue_(octetsPerValue), sex_(sex), length_(0) {
        ASSERT_require(1 == octetsPerValue || sex != ByteOrder::ORDER_UNSPECIFIED);
        ASSERT_require(octetsPerValue <= sizeof(size_t));
    }
 
  public:
    static Ptr instance(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED) {
        return Ptr(new BasicLengthEncodingScheme(octetsPerValue, sex));
    }
    virtual Ptr         clone() const override { return Ptr(new BasicLengthEncodingScheme(*this)); }
    virtual std::string name() const override;
    virtual Octets      encode(size_t) override;
    virtual State       decode(Octet) override;
    virtual size_t      consume() override;
    virtual void        reset() override;
};
 
BasicLengthEncodingScheme::Ptr
basicLengthEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);
 
class ROSE_DLL_API CodePointPredicate: public Sawyer::SharedObject {
  public:
    virtual ~CodePointPredicate() {}
 
    typedef Sawyer::SharedPointer<CodePointPredicate> Ptr;
 
    virtual std::string name() const = 0;
 
    virtual bool isValid(CodePoint) = 0;
};
 
class ROSE_DLL_API PrintableAscii: public CodePointPredicate {
  protected:
    PrintableAscii() {}
 
  public:
    static Ptr          instance() { return Ptr(new PrintableAscii); }
    virtual std::string name() const override { return "printable ASCII"; }
    virtual bool        isValid(CodePoint) override;
};
 
PrintableAscii::Ptr printableAscii();
 
class ROSE_DLL_API AnyCodePoint: public CodePointPredicate {
  protected:
    AnyCodePoint() {}
 
  public:
    static Ptr          instance() { return Ptr(new AnyCodePoint); }
    virtual std::string name() const override { return "any code point"; }
    virtual bool        isValid(CodePoint) override { return true; }
};
 
AnyCodePoint::Ptr anyCodePoint();
 
class ROSE_DLL_API StringEncodingScheme: public Sawyer::SharedObject {
  protected:
    State                        state_ = INITIAL_STATE; // decoding state
    CodePoints                   codePoints_;            // unconsumed code points
    size_t                       nCodePoints_ = 0;       // number of code points decoded since reset
    CharacterEncodingForm::Ptr   cef_;
    CharacterEncodingScheme::Ptr ces_;
    CodePointPredicate::Ptr      cpp_;
 
  protected:
    StringEncodingScheme() {}
 
    StringEncodingScheme(
      const CharacterEncodingForm::Ptr& cef, const CharacterEncodingScheme::Ptr& ces, const CodePointPredicate::Ptr& cpp
    ) : cef_(cef), ces_(ces), cpp_(cpp) {}
 
  public:
    virtual ~StringEncodingScheme() {}
 
    typedef Sawyer::SharedPointer<StringEncodingScheme> Ptr;
 
    virtual std::string name() const = 0;
 
    virtual Ptr clone() const = 0;
 
    virtual Octets encode(const CodePoints&) = 0;
 
    State state() const { return state_; }
 
    virtual State decode(Octet) = 0;
 
    CodePoints consume();
 
    const CodePoints& codePoints() const { return codePoints_; }
 
    size_t length() const { return nCodePoints_; }
 
    virtual void reset();
 
    CharacterEncodingForm::Ptr characterEncodingForm() const { return cef_; }
    void                       characterEncodingForm(const CharacterEncodingForm::Ptr& cef) { cef_ = cef; }
    CharacterEncodingScheme::Ptr characterEncodingScheme() const { return ces_; }
    void                         characterEncodingScheme(const CharacterEncodingScheme::Ptr& ces) { ces_ = ces; }
    CodePointPredicate::Ptr codePointPredicate() const { return cpp_; }
    void                    codePointPredicate(const CodePointPredicate::Ptr& cpp) { cpp_ = cpp; }
};
 
class ROSE_DLL_API LengthEncodedString: public StringEncodingScheme {
    LengthEncodingScheme::Ptr les_;
    Sawyer::Optional<size_t>  declaredLength_; // decoded length
  protected:
    LengthEncodedString(
      const LengthEncodingScheme::Ptr& les, const CharacterEncodingForm::Ptr& cef,
      const CharacterEncodingScheme::Ptr& ces, const CodePointPredicate::Ptr& cpp
    ) : StringEncodingScheme(cef, ces, cpp), les_(les) {}
 
  public:
    typedef Sawyer::SharedPointer<LengthEncodedString> Ptr;
 
    static Ptr instance(
      const LengthEncodingScheme::Ptr& les, const CharacterEncodingForm::Ptr& cef,
      const CharacterEncodingScheme::Ptr& ces, const CodePointPredicate::Ptr& cpp
    ) {
        return Ptr(new LengthEncodedString(les, cef, ces, cpp));
    }
    virtual StringEncodingScheme::Ptr clone() const override {
        LengthEncodingScheme::Ptr    les  = les_->clone();
        CharacterEncodingForm::Ptr   cef  = cef_->clone();
        CharacterEncodingScheme::Ptr ces  = ces_->clone();
        CodePointPredicate::Ptr      cpp  = cpp_; // not cloned since they have no state
        LengthEncodedString*         inst = new LengthEncodedString(les, cef, ces, cpp);
        inst->state_                      = state_;
        inst->codePoints_                 = codePoints_;
        inst->nCodePoints_                = nCodePoints_;
        inst->declaredLength_             = declaredLength_;
        return Ptr(inst);
    }
    virtual std::string name() const override;
    virtual Octets      encode(const CodePoints&) override;
    virtual State       decode(Octet) override;
    virtual void        reset() override;
 
    Sawyer::Optional<size_t> declaredLength() const { return declaredLength_; }
 
    LengthEncodingScheme::Ptr lengthEncodingScheme() const { return les_; }
    void                      lengthEncodingScheme(const LengthEncodingScheme::Ptr& les) { les_ = les; }
};
 
LengthEncodedString::Ptr lengthEncodedString(
  const LengthEncodingScheme::Ptr& les, const CharacterEncodingForm::Ptr& cef, const CharacterEncodingScheme::Ptr& ces,
  const CodePointPredicate::Ptr& cpp
);
 
LengthEncodedString::Ptr
lengthEncodedPrintableAscii(size_t lengthSize, ByteOrder::Endianness order = ByteOrder::ORDER_UNSPECIFIED);
 
LengthEncodedString::Ptr
lengthEncodedPrintableAsciiWide(size_t lengthSize, ByteOrder::Endianness order, size_t charSize);
 
class ROSE_DLL_API TerminatedString: public StringEncodingScheme {
    CodePoints                  terminators_;
    Sawyer::Optional<CodePoint> terminated_; // decoded termination
  protected:
    TerminatedString(
      const CharacterEncodingForm::Ptr& cef, const CharacterEncodingScheme::Ptr& ces,
      const CodePointPredicate::Ptr& cpp, const CodePoints& terminators
    ) : StringEncodingScheme(cef, ces, cpp), terminators_(terminators) {}
 
  public:
    typedef Sawyer::SharedPointer<TerminatedString> Ptr;
 
    static Ptr instance(
      const CharacterEncodingForm::Ptr& cef, const CharacterEncodingScheme::Ptr& ces,
      const CodePointPredicate::Ptr& cpp, const CodePoints& terminators
    ) {
        return Ptr(new TerminatedString(cef, ces, cpp, terminators));
    }
    static Ptr instance(
      const CharacterEncodingForm::Ptr& cef, const CharacterEncodingScheme::Ptr& ces,
      const CodePointPredicate::Ptr& cpp, CodePoint terminator = 0
    ) {
        return Ptr(new TerminatedString(cef, ces, cpp, CodePoints(1, terminator)));
    }
    virtual StringEncodingScheme::Ptr clone() const override {
        CharacterEncodingForm::Ptr   cef  = cef_->clone();
        CharacterEncodingScheme::Ptr ces  = ces_->clone();
        CodePointPredicate::Ptr      cpp  = cpp_; // not cloned since they have no state
        TerminatedString*            inst = new TerminatedString(cef, ces, cpp, terminators_);
        inst->state_                      = state_;
        inst->codePoints_                 = codePoints_;
        inst->nCodePoints_                = nCodePoints_;
        inst->terminated_                 = terminated_;
        return Ptr(inst);
    }
    virtual std::string name() const override;
    virtual Octets      encode(const CodePoints&) override;
    virtual State       decode(Octet) override;
    virtual void        reset() override;
 
    Sawyer::Optional<CodePoint> terminated() const { return terminated_; }
 
    const CodePoints& terminators() const { return terminators_; }
    CodePoints&       terminators() { return terminators_; }
};
 
TerminatedString::Ptr nulTerminatedPrintableAscii();
 
TerminatedString::Ptr nulTerminatedPrintableAsciiWide(size_t charSize, ByteOrder::Endianness order);
 
class ROSE_DLL_API EncodedString {
    StringEncodingScheme::Ptr encoder_; // how string is encoded
    AddressInterval           where_;   // where encoded string is located
  public:
    EncodedString() {}
    EncodedString(const StringEncodingScheme::Ptr& encoder, const AddressInterval& where) :
      encoder_(encoder), where_(where) {}
 
    StringEncodingScheme::Ptr encoder() const { return encoder_; }
 
    const AddressInterval& where() const { return where_; }
 
    Address address() const { return where_.least(); }
 
    size_t size() const { return where_.size(); }
 
    size_t length() const { return encoder_->length(); }
 
    const CodePoints& codePoints() const { return encoder_->codePoints(); }
 
    std::string narrow() const;
 
    std::wstring wide() const;
 
    void decode(const MemoryMap&);
};
 
class ROSE_DLL_API StringFinder {
  public:
    struct Settings {
        size_t minLength;
 
        size_t maxLength;
 
        size_t maxOverlap;
 
        bool keepingOnlyLongest;
 
        Sawyer::Optional<StringFilter> filter;
 
        Settings() : minLength(5), maxLength(-1), maxOverlap(8), keepingOnlyLongest(true) {}
    };
 
  private:
    Settings                               settings_;             // command-line settings for this analysis
    bool                                   discardingCodePoints_; // whether to store decoded code points
    std::vector<StringEncodingScheme::Ptr> encoders_;             // encodings to use when searching
    std::vector<EncodedString>             strings_;              // strings that have been found
 
  public:
    StringFinder() : discardingCodePoints_(false) {}
 
    const Settings& settings() const { return settings_; }
    Settings&       settings() { return settings_; }
    bool          discardingCodePoints() const { return discardingCodePoints_; }
    StringFinder& discardingCodePoints(bool b) {
        discardingCodePoints_ = b;
        return *this;
    }
    const std::vector<StringEncodingScheme::Ptr>& encoders() const { return encoders_; }
    std::vector<StringEncodingScheme::Ptr>&       encoders() { return encoders_; }
    static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings&);
    Sawyer::CommandLine::SwitchGroup        commandLineSwitches();
    StringFinder& insertCommonEncoders(ByteOrder::Endianness);
 
    StringFinder& insertUncommonEncoders(ByteOrder::Endianness);
 
    StringFinder& reset() {
        strings_.clear();
        return *this;
    }
 
    StringFinder& find(const MemoryMap::ConstConstraints&, Sawyer::Container::MatchFlags flags = 0);
 
    StringFinder& find(SgAsmInterpretation* interp, std::vector<std::string>&);
 
    const std::vector<EncodedString>& strings() const { return strings_; }
    std::vector<EncodedString>&       strings() { return strings_; }
    std::ostream& print(std::ostream&) const;
};
 
std::ostream& operator<<(std::ostream&, const StringFinder&);
 
} // namespace Strings
} // namespace BinaryAnalysis
} // namespace Rose
 
#endif
#endif