MTAResultValidator.h

Go to the documentation of this file.

/*
 * MTAResultValidator.h
 *
 *  Created on: 29/06/2015
 *      Author: Peng Di and Ding Ye
 */
 
#ifndef MTARESULTVALIDATOR_H_
#define MTARESULTVALIDATOR_H_
 
#include "MTA/MHP.h"
 
namespace SVF
{
typedef unsigned NodeID;
 
class MTAResultValidator
{
 
public:
    typedef int INTERLEV_FLAG;
    MTAResultValidator(MHP* mh) :
        mhp(mh)
    {
        tcg = mhp->getThreadCallGraph();
        tdAPI = tcg->getThreadAPI();
        mod = mhp->getTCT()->getSVFModule();
    }
    // Destructor
    ~MTAResultValidator()
    {
    }
 
    // Analysis
    void analyze();
    inline SVFModule* getModule() const
    {
        return mod;
    }
protected:
 
    /*
     * Assistant functions
     */
 
    // Split string
    std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems);
    std::vector<std::string> split(const std::string &s, char delim);
 
    // Get special arguments of given call sites
    NodeID getIntArg(const Instruction* inst, unsigned int arg_num);
    std::vector<std::string> getStringArg(const Instruction* inst, unsigned int arg_num);
    CallStrCxt getCxtArg(const Instruction* inst, unsigned int arg_num);
 
    /*
     * Get the previous LoadInst or StoreInst from Instruction "I" in the
     * same BasicBlock. Return nullptr if none exists.
     */
    const Instruction* getPreviousMemoryAccessInst(const Instruction* I);
 
    // Compare two cxts
    bool matchCxt(const CallStrCxt cxt1, const CallStrCxt cxt2) const;
 
    // Dump calling context information
    void dumpCxt(const CallStrCxt& cxt) const;
 
    void dumpInterlev(NodeBS& lev);
 
    // Get the validation result string of a single validation scenario.
    inline std::string getOutput(const char *scenario, bool analysisRes);
    inline std::string getOutputforInterlevAnalysis(const char *scenario, INTERLEV_FLAG analysisRes);
 
    /*
     * Collect the callsite targets for validations.
     * The targets are labeled by "cs1:", "cs2:"... that are the names of its basic blocks.
     * The collected targets are stored in csnumToInstMap that maps label "cs1" to its Callsite.
     */
    bool collectCallsiteTargets();
 
    /*
     * Collect the CxtThread targets for validations.
     * The collected targets are stored in vthdToCxt that maps vthd to cxt.
     */
    bool collectCxtThreadTargets();
 
    /*
     * Collect TCT targets for validations.
     * The collected targets are stored in rthdToChildren.
     */
    bool collectTCTTargets();
 
    /*
     * Collect the thread interleaving targets for validations.
     * The collected targets are stored in instToTSMap and threadStmtToInterLeaving.
     */
    bool collectInterleavingTargets();
 
    /*
     * Perform validation for Cxtthread.
     * If correct, the validator maps given thread vthd to static CxtThread rthd stored in vthdTorthd.
     */
    bool validateCxtThread();
 
    /*
     * Perform validation for TCT.
     */
    bool validateTCT();
 
    /*
     * Perform validation for thread interleaving.
     */
    INTERLEV_FLAG validateInterleaving();
 
private:
 
    typedef Map<NodeID, const SVFInstruction*> csnumToInst;
    typedef Map<NodeID, CallStrCxt> vthdToCxtMap;
    typedef Map<NodeID, NodeID> vthdTorthdMap;
    typedef Map<NodeID, NodeID> rthdTovthdMap;
 
    typedef Map<NodeID, Set<NodeID>> rthdToChildrenMap;
 
    MHP::InstToThreadStmtSetMap instToTSMap; // Map a instruction to CxtThreadStmtSet
    MHP::ThreadStmtToThreadInterleav threadStmtToInterLeaving; 
 
    static constexpr char const *CXT_THREAD = "CXT_THREAD";
    static constexpr char const *INTERLEV_ACCESS = "INTERLEV_ACCESS";
    static constexpr char const *TCT_ACCESS = "TCT_ACCESS";
 
    ThreadAPI* tdAPI;
    ThreadCallGraph* tcg;
    MHP* mhp;
    vthdToCxtMap vthdToCxt;
    vthdTorthdMap vthdTorthd;
    rthdTovthdMap rthdTovthd;
    csnumToInst csnumToInstMap;
    rthdToChildrenMap rthdToChildren;
    SVFModule* mod;
 
    static const INTERLEV_FLAG INTERLEV_TRUE = 0x01;
    static const INTERLEV_FLAG INTERLEV_IMPRECISE = 0x02;
    static const INTERLEV_FLAG INTERLEV_UNSOUND = 0x04;
};
 
 
 
class RaceResultValidator
{
public:
    typedef int RC_FLAG;
 
    class AccessPair
    {
    public:
        AccessPair(const Instruction* I1, const Instruction* I2,
                   const RC_FLAG flags) :
            I1(I1), I2(I2), flags(flags)
        {
        }
 
 
        inline bool isFlaged(const RC_FLAG flag) const
        {
            return flags & flag;
        }
        inline const Instruction* getInstruction1() const
        {
            return I1;
        }
        inline const Instruction* getInstruction2() const
        {
            return I2;
        }
 
    private:
        const Instruction* I1;
        const Instruction* I2;
        RC_FLAG flags;
    };
 
    virtual ~RaceResultValidator()
    {
        release();
    }
 
    void init(SVFModule* M)
    {
        this->M = M;
        selectedValidationScenarios = RC_MHP | RC_ALIASES | RC_PROTECTED | RC_RACE;
        collectValidationTargets();
    }
 
    void analyze()
    {
        validateAll();
    }
 
    void release()
    {
    }
 
    inline bool hasValidationTarget() const
    {
        return !accessPairs.empty();
    }
 
protected:
 
    virtual bool mayAccessAliases(const Instruction* I1,
                                  const Instruction* I2)
    {
        selectedValidationScenarios &= ~RC_ALIASES;
        return true;
    }
    virtual bool mayHappenInParallel(const Instruction* I1,
                                     const Instruction* I2)
    {
        selectedValidationScenarios &= ~RC_MHP;
        return true;
    }
    virtual bool protectedByCommonLocks(const Instruction* I1,
                                        const Instruction* I2)
    {
        selectedValidationScenarios &= ~RC_PROTECTED;
        return true;
    }
    virtual bool mayHaveDataRace(const Instruction* I1,
                                 const Instruction* I2)
    {
        selectedValidationScenarios &= ~RC_RACE;
        return true;
    }
 
    void collectValidationTargets()
    {
        // Collect call sites of all RC_ACCESS function calls.
        std::vector<const CallBase*> csInsts;
        const Function* F = nullptr;
        for (Module &M : LLVMModuleSet::getLLVMModuleSet()->getLLVMModules())
        {
            for(auto it = M.begin(); it != M.end(); it++)
            {
                const std::string fName = (*it).getName().str();
                if(fName.find(RC_ACCESS) != std::string::npos)
                {
                    F = &(*it);
                    break;
                }
            }
        }
        if (!F)     return;
 
        for (Value::const_use_iterator it = F->use_begin(), ie =
                    F->use_end(); it != ie; ++it)
        {
            const Use *u = &*it;
            const Value *user = u->getUser();
            if(LLVMUtil::isCallSite(user))
            {
                const CallBase* csInst = LLVMUtil::getLLVMCallSite(user);
                csInsts.push_back(csInst);
            }
        }
        assert(csInsts.size() % 2 == 0 && "We should have RC_ACCESS called in pairs.");
 
        // Sort the validation sites according to their ids.
        std::sort(csInsts.begin(), csInsts.end(), compare);
 
        // Generate access pairs.
        for (int i = 0, e = csInsts.size(); i != e;)
        {
            const CallBase* CI1 = csInsts[i++];
            const CallBase* CI2 = csInsts[i++];
            const ConstantInt* C = SVFUtil::dyn_cast<ConstantInt>(CI1->getArgOperand(1));
            assert(C);
            const Instruction* I1 = getPreviousMemoryAccessInst(CI1);
            const Instruction* I2 = getPreviousMemoryAccessInst(CI2);
            assert(I1 && I2 && "RC_ACCESS should be placed immediately after the target memory access.");
            RC_FLAG flags = C->getZExtValue();
            accessPairs.push_back(AccessPair(I1, I2, flags));
        }
    }
 
    void validateAll()
    {
        SVFUtil::outs() << SVFUtil::pasMsg(" --- Analysis Result Validation ---\n");
 
        // Iterate every memory access pair to perform the validation.
        for (int i = 0, e = accessPairs.size(); i != e; ++i)
        {
            const AccessPair &ap = accessPairs[i];
            const Instruction* I1 = ap.getInstruction1();
            const Instruction* I2 = ap.getInstruction2();
 
            bool mhp = mayHappenInParallel(I1, I2);
            bool alias = mayAccessAliases(I1, I2);
            bool protect = protectedByCommonLocks(I1, I2);
            bool racy = mayHaveDataRace(I1, I2);
 
            SVFUtil::outs() << "For the memory access pair at ("
                            << LLVMModuleSet::getLLVMModuleSet()->getSVFValue(I1)->getSourceLoc() << ", "
                            << LLVMModuleSet::getLLVMModuleSet()->getSVFValue(I2)->getSourceLoc() << ")\n";
            if (selectedValidationScenarios & RC_ALIASES)
            {
                SVFUtil::outs() << "\t"
                                << getOutput("ALIASES", alias, ap.isFlaged(RC_ALIASES))
                                << "\n";
            }
            if (selectedValidationScenarios & RC_MHP)
            {
                SVFUtil::outs() << "\t"
                                << getOutput("MHP", mhp, ap.isFlaged(RC_MHP)) << "\n";
            }
            if (selectedValidationScenarios & RC_PROTECTED)
            {
                SVFUtil::outs() << "\t"
                                << getOutput("PROTECT", protect,
                                             ap.isFlaged(RC_PROTECTED)) << "\n";
            }
            if (selectedValidationScenarios & RC_RACE)
            {
                SVFUtil::outs() << "\t"
                                << getOutput("RACE", racy, ap.isFlaged(RC_RACE))
                                << "\n";
            }
        }
 
        SVFUtil::outs() << "\n";
    }
 
    inline std::string getOutput(const char *scenario,
                                 bool analysisRes, bool expectedRes)
    {
        std::string ret(scenario);
        ret += "\t";
        if (expectedRes)
            ret += " T: ";
        else
            ret += " F: ";
        if (analysisRes == expectedRes)
            ret += SVFUtil::sucMsg("SUCCESS");
        else
            ret += SVFUtil::errMsg("FAILURE");
        return ret;
    }
 
private:
    SVFModule* M;
    std::vector<AccessPair> accessPairs;
    RC_FLAG selectedValidationScenarios;
 
    static bool compare(const CallBase* CI1, const CallBase* CI2)
    {
        const Value *V1 = CI1->getArgOperand(0);
        const Value *V2 = CI2->getArgOperand(0);
        const ConstantInt* C1 = SVFUtil::dyn_cast<ConstantInt>(V1);
        const ConstantInt* C2 = SVFUtil::dyn_cast<ConstantInt>(V2);
        assert(0 != C1 && 0 != C2);
        return C1->getZExtValue() < C2->getZExtValue();
    }
 
    const Instruction* getPreviousMemoryAccessInst(
        const Instruction* I)
    {
        I = I->getPrevNode();
        while (I)
        {
            if (SVFUtil::isa<LoadInst, StoreInst>(I))
                return I;
 
            const SVFInstruction* inst = LLVMModuleSet::getLLVMModuleSet()->getSVFInstruction(I);
 
            if (const SVFFunction *callee = SVFUtil::getCallee(inst))
            {
                if (callee->getName().find("llvm.memset") != std::string::npos)
                    return I;
 
            }
            I = I->getPrevNode();
        }
        return nullptr;
    }
 
 
    static const RC_FLAG RC_MHP = 0x01;
    static const RC_FLAG RC_ALIASES = 0x02;
    static const RC_FLAG RC_PROTECTED = 0x04;
    static const RC_FLAG RC_RACE = 0x10;
 
    static constexpr char const *RC_ACCESS = "RC_ACCESS";
};
}   // namespace SVF end
#endif /* MTARESULTVALIDATOR_H_ */