### BEGIN LICENSE ###
### Use of the triage tools and related source code is subject to the terms
### of the license below.
###
### ------------------------------------------------------------------------
### Copyright (C) 2011 Carnegie Mellon University. All Rights Reserved.
### Portions Copyright 2013 BlackBerry Ltd. All Rights Reserved.
### ------------------------------------------------------------------------
### Redistribution and use in source and binary forms, with or without
### modification, are permitted provided that the following conditions are
### met:
###
### 1. Redistributions of source code must retain the above copyright
###    notice, this list of conditions and the following acknowledgments
###    and disclaimers.
###
### 2. Redistributions in binary form must reproduce the above copyright
###    notice, this list of conditions and the following disclaimer in the
###    documentation and/or other materials provided with the distribution.
###
### 3. The names "Department of Homeland Security," "Carnegie Mellon
###    University," "CERT" and/or "Software Engineering Institute" shall
###    not be used to endorse or promote products derived from this software
###    without prior written permission. For written permission, please
###    contact permission@sei.cmu.edu.
###
### 4. Products derived from this software may not be called "CERT" nor
###    may "CERT" appear in their names without prior written permission of
###    permission@sei.cmu.edu.
###
### 5. Redistributions of any form whatsoever must retain the following
###    acknowledgment:
###
###    "This product includes software developed by CERT with funding
###     and support from the Department of Homeland Security under
###     Contract No. FA 8721-05-C-0003."
###
### THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
### CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
### EXPRESS OR IMPLIED, AS TO ANY MATTER, AND ALL SUCH WARRANTIES, INCLUDING
### WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE
### EXPRESSLY DISCLAIMED. WITHOUT LIMITING THE GENERALITY OF THE FOREGOING,
### CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND
### RELATING TO EXCLUSIVITY, INFORMATIONAL CONTENT, ERROR-FREE OPERATION,
### RESULTS TO BE OBTAINED FROM USE, FREEDOM FROM PATENT, TRADEMARK AND
### COPYRIGHT INFRINGEMENT AND/OR FREEDOM FROM THEFT OF TRADE SECRETS.
### END LICENSE ###
'''
A collection of Python objects that wrap and extend the GDB Python API.

This file contains base class logic for GDB wrapper object as well as
x86-specific logic. Someday these should be separated.
'''
try:
    import gdb
except ImportError as e:
    raise ImportError("This script must be run in GDB: ", str(e))

import hashlib
import os
import re
import warnings

from lib.gdb_wrapper.elf import read_elf_sects
from lib.tools import AttrDict, memoized

def gdb_uint(gdb_value):
    '''
    Returns a gdb.Value of an unsigned GDB Type corresponding to the
    supplied gdb.Value.

    The GDB module (as of 7.3) evaluates expressions including certain
    registers (any register that isn't eip, esp, or ebp) to a signed type.
    So, for example, '$edx' is considered negative if the highest order bit is
    set. We treat evaluated expressions as addresses sometimes, such as
    when comparing an evaluated expression to si_addr (which is of an
    unsigned GDB.Value type). This method can be used to ensure the types
    agree and that arithmetic/boolean operations evaluate as expected.
    '''
    import sys
    pyint = int(gdb_value.cast(gdb.lookup_type("unsigned long")))
    # see https://docs.python.org/2/library/platform.html#cross-platform
    if sys.maxsize > 2**32:
        return pyint & 0xFFFFFFFFFFFFFFFF
    return pyint & 0xFFFFFFFF

class GdbWrapperError(RuntimeError):
    '''
    Base class for errors in this module
    '''
    pass

class ProcMaps(list):
    '''
    A list of process address mappings. This object should only be instantiated
    when the Inferior is running, otherwise the string parsing may fail.
    '''
    _re_info_target = re.compile(r"""^\s+`(?P<file>.*?)',\s+file\s+type |
                                     ^\s+(?P<start>0x[0-9A-Fa-f]+)\s+-\s+
                                     (?P<end>0x[0-9A-Fa-f]+)\s+is\s+
                                     (?P<section>.*?)(\s+in\s+(?P<lib>.*?)(\.so[\.0-9]*)?)?$""", re.MULTILINE|re.VERBOSE)
    _re_gdb_sect_info = re.compile(r"^\s+(?P<start>0x[A-Fa-f0-9]+)->(?P<end>0x[A-Fa-f0-9]+) at 0x[A-Fa-f0-9]+: (?P<sect>[^\s]+)", re.MULTILINE)

    def __init__(self):
        '''
        Queries the GDB Python API for the process address space, parses
        it, and appends it to self
        '''
        self._common_init()
        mapstr = str(gdb.execute("info proc map", False, True))
        header_pos = mapstr.find("Start Addr")
        if header_pos == -1:
            raise GdbWrapperError("Unable to parse \"info proc map\" string")
        maplines = mapstr[header_pos:].splitlines()[1:]
        for line in maplines:
            line = line.split()
            start, end, size, offset = tuple(int(i, 16) for i in line[0:4])
            name = " ".join(line[4:])
            ad = AttrDict(start=start, end=end, size=size,
                  offset=offset, name=name)
            self.append(ad)

    def _common_init(self):
        '''
        Performs init common to this class and some subclasses.
        '''
        list.__init__(self)
        self._files = set()

    def __str__(self):
        result = ["{:10} {:10} {:10} {:10} {} {}".format("start", "end",
            "size", "offset", "name", "sect")]
        for m in self:
            result.append("{0.start:#08x} {0.end:#08x} {0.size:#08x} " +\
                "{0.offset:#08x} {0.name} {1}".format(m,
                    getattr(m, "sect", "?")))
        result.append("")
        return "\n".join(result)

    def findByName(self, name):
        '''
        Returns the process address mapping whose name matches name
        or None if no such mapping is found in self.
        '''
        for sect in self:
            if sect.name == name:
                return sect
        return None

    def findByAddr(self, addr):
        '''
        Returns the process address mapping that addr falls in,
        or None if no such mapping is found in self.
        '''
        result = None
        for sect in self:
            if sect.start <= addr < sect.end:
                if result is None or sect.size < result.size:
                    result = sect
        return result

class Instruction(object):
    '''
    A disassembled instruction. Notable attributes include:

    gdbstr - the original string of disassembly that was used to
        populate this instance
    operands - a list of Operand instances corresponding this
        Instruction's operands, ordered by operand_order
        See Operand class documentation for details
    mnemonic - the instruction mnemonic (ex: "pop" or "rep mov")
    dest - the destination Operand of this instruction (optional--
        only exists if this Instruction has a logical destination
        operand)
    source - the source Operand of this instruction (optional)
    aux - the aux Operand of this instruction (optional)
    '''
    _re_hex_int = re.compile(r"(0x[A-Fa-f0-9]+)")
    _re_dis_fail = re.compile(r""".*(<internal\sdisassembler\serror>|
                                     No\sfunction\scontains\sspecified\saddress).*""", re.VERBOSE)
    _x86_prefixes = ["rep", "repe", "repz", "repne", "repnz"]

    def __init__(self, gdbstr):
        '''
        Parses gdbstr to populate self; this method only covers parsing that
        is common across processor architectures. The remainder of the parsing
        is implemented in subclasses.
        '''
        self.gdbstr = gdbstr
        if self._re_dis_fail.match(self.gdbstr):
            raise GdbWrapperError("Disassembler error detected: {}".format(self.gdbstr))
        self.operands = []
        self.source = None
        self.dest = None
        self.aux = None

    def __str__(self):
        return self.gdbstr

class x86Instruction(Instruction):
    '''
    A disassembled Intel instruction. See Instruction class comments for more
    details.
    '''

    def __init__(self, gdbstr):
        '''
        Parses gdbstr to populate self.
        '''
        Instruction.__init__(self, gdbstr)

        # strip indicator
        if self.gdbstr[0:2] == "=>":
            self.gdbstr = self.gdbstr[2:]

        # strip hints
        c = 0
        s = self.gdbstr
        self.gdbstr = ""
        for i in range(0, len(s)):
            if s[i] == "<":
                c += 1
                continue
            elif s[i] == ">":
                c -= 1
                continue
            if c > 0:
                continue
            self.gdbstr += s[i]

        toks = []
        for t in self.gdbstr.split():
            t = t.strip().strip(":")
            if t:
                toks.append(t)
        self.addr = int(toks[0], 16)

        # get mnemonic
        if toks[1] in self._x86_prefixes: # handle rep* prefixes
            self.mnemonic = " ".join(toks[1:3])
            self.inst = " ".join(toks[3:])
        else:
            self.mnemonic = toks[1]
            self.inst = " ".join(toks[2:])

        if self.inst == "": # handle "ret", "iret", et al.
            return

        # get operands
        self.operands = [Operand(o) for o in self.inst.split(",")]
        for a, o in zip(("dest", "source", "aux"), self.operands):
            setattr(self, a, o)

class Operand(object):
    '''
    A disassembled instruction operand that can be evaluated. Notable
    attributes include:

    gdbstr - the original string of disassembled operand that was used to
        populate this instance
    is_pointer - True if this operand represents a pointer, False otherwise.
        For example, "DWORD PTR [eax]" is considered a pointer, "eax" is not.
    regs - a list of strings representing the registers used in this Operand
    '''
    _re_addr = re.compile(r""".*\[(.*)\]  | # DWORD PTR [eax+0x1234]
                              .*\:(.*)      # DWORD PTR gs:0x18
                           """, re.VERBOSE)
    _re_p_regs = re.compile(r"eiz|riz")
    _re_regstrs = re.compile(
                r"""^([a-z]{1,5}\d{0,2}[a-z]{0,1})(?=\s*[\*\+-])                | # "(eax)+0x1234"
                     (?<=[\*\+-])\s*([a-z]{1,5}\d{0,2}[a-z]{0,1})(?=[\s*\*\+-]) | # "xmm5+(al)-0x1234"
                     (?<=[\*\+-])\s*([a-z]{1,5}\d{0,2}[a-z]{0,1})$              | # "eax+4* (esi)"
                    ^([a-z]{1,5}\d{0,2}[a-z]{0,1})$                               # "(edi)"
                 """, re.VERBOSE)
    _re_fpu_stack = re.compile(r"(st\(.*\))")

    def __init__(self, gdbstr):
        '''
        Parses gdbstr to populate self.  ex gdbstr="BYTE PTR es:[edi]"
        '''
        self.gdbstr = gdbstr
        gdbstr = gdbstr.split("<")[0] # get rid of "<addr resolutions>"

        # get addr
        addr = self._re_addr.match(gdbstr) # ignores segment regs
        if addr:
            self.is_pointer = True
            expr = [m for m in addr.groups() if m][0]
        else:
            self.is_pointer = False
            expr = gdbstr

        # eiz(x86) and riz(64) are pseudo-index registers that
        # the CPU always evaluates to 0. GDB types them as void (DNE)
        # which can cause a type error when evaluating expression via GDB,
        # so we substitute immediate zeros
        expr = self._re_p_regs.sub("0", expr)

        self.regs = [t.group() for t in self._re_regstrs.finditer(expr)]
        # prep for GDB evaluation. ex: "edx+0x12" becomes "$edx+0x12"
        self.expr = self._re_regstrs.sub(
                      (lambda mo: "${}".format([mg for mg in mo.groups() if mg][0])),
                      expr)

    def eval(self):
        '''
        Returns the integer value of this operand as evaluated by GDB. For
        example, if eax = 0x5 and this operand is DWORD PTR[eax + 0x100],
        eval would be 0x105 (a GDB.Value)
        '''
        if "mm" in " ".join(self.regs) or self._re_fpu_stack.match(self.gdbstr):
            return 0xDEADBEEF
        else:
            # Some GDBs (GDB 7.2 Fedora vs. Ubuntu/Debian) don't compare
            # signed and unsigned integer types consistently. gdb_uint
            # is a workaround
            return gdb_uint(gdb.parse_and_eval(self.expr))

    def __str__(self):
        return self.gdbstr

class Backtrace(list):
    '''
    A backtrace composed of a list of GDB Frames (ordered from innermost to
    outermost) and other attributes, including:

    hash - an object that can be used to determine uniqueness: note that
        Backtrace does not implement hashing from the Python data model (yet)
    abnormal_termination - set to True if GDB's backtrace unwind terminated
        abnormally, such as in the case of stack corruption
    '''
    def __init__(self, target, blacklist=None, major_depth=5, limit=0):
        '''
        Uses the GDB API to populate self. Any frames in
        blacklist are marked as such. The first non-blacklisted,
        major_depth frames are used to calculate the
        backtrace's major hash.
        '''
        list.__init__(self)
        self.blacklist = blacklist

        frame = self._next_frame()
        hc = 0
        i = 0
        major = ""
        minor = ""
        self.abnormal_termination = False
        while frame:
            frame = self._next_frame(target, frame, i)
            if not frame:
                break

            # The check below is a workaround for a known libc/gdb runaway
            # backtrace issue, see
            # http://sourceware.org/ml/libc-alpha/2012-03/msg00573.html
            if frame.name() and "libc_start_main" in frame.name():
                break

            if not self._in_blacklist(frame):
                if hc < major_depth:
                    major = hashlib.md5((major + str(frame)).encode()).hexdigest()
                hc += 1
            else:
                frame.blacklisted = True
            # logic change - use ALL frames for the minor hash
            minor = hashlib.md5((minor + str(frame)).encode()).hexdigest()
            self.append(frame)

            # some versions of the GDB Python API do not expose a frame unwind
            # error sentinel; if it is not available a hardcoded value based on
            # an enum from GDB's gdb/frames.h is used
            unwind_error = getattr(gdb, "FRAME_UNWIND_FIRST_ERROR", 3)
            if frame.unwind_stop_reason() >= unwind_error:
                self.abnormal_termination = True
                break

            try:
                frame = frame.older()
            except RuntimeError:
                self.abnormal_termination = True
                break
            i += 1

            if limit and i >= limit:
                break

        # if all major frames were blacklisted, call the major hash 0x0
        # but make it 32 bytes long to make parsing easy.
        if len(major) == 0:
            major = '0' * 32

        self.hash = AttrDict(major=major, minor=minor)

    def _next_frame(self, target=None, frame=None, i=None):
        '''
        Gets the next frame (the frame after 'frame').
        If called without params (or if target is None, at least) then the
        innermost frame is obtained from GDB.
        '''
        if not target:
            return gdb.selected_frame()
        return Frame(target, frame, i)

    def _in_blacklist(self, frame):
        '''
        Returns True if frame is in self.blacklist, False otherwise.
        '''
        if not self.blacklist:
            return False
        if frame.name() in self.blacklist.functions:
            return True
        if frame.mapped_region and \
           self.blacklist.map_regex.match(frame.mapped_region.name):
            return True
        return False

    def __str__(self):
        result = [str(f) for f in self]
        if self.abnormal_termination:
            reason = self[-1].unwind_stop_reason()
            result.append("abnormal stack unwind termination: {}".format(
                gdb.frame_stop_reason_string(reason)))
        return "\n".join(result)

class Frame(object):
    '''
    Wrapper for gdb.Frame. Adds frame position, pretty string, etc.

    Note: Because GDB Python API classes cannot be inherited, this class
    overloads __getattr__ to pass method calls to gdb.Frame. This may cause
    some issues with getting/setting this class's state, such as during
    pickling.
    '''
    def __init__(self, target, gdb_frame, position=None):
        self.gdb_frame = gdb_frame
        self.position = position
        self.blacklisted = False
        self.mapped_region = target.procmaps().findByAddr(self.pc())
        sym_addr = target.sym_addr(self.pc())
        if sym_addr is None:
            try:
                sym_addr = self.mapped_region.start
            except AttributeError:
                sym_addr = 0
        self.offset = self.pc() - sym_addr

    def __getattr__(self, name):
        return getattr(self.gdb_frame, name)

    def __str__(self):
        desc = "#{:3d} {} at {:#x} in {}".format(self.position, self.name(), self.pc(),
                                self.mapped_region.name if self.mapped_region else "?")
        if self.blacklisted:
            desc += " (BL)"
        return desc

    def terse(self):
        out = self.mapped_region.name if self.mapped_region else "Unknown"
        name = self.name()
        if name is not None:
            out = "{}!{}".format(out, name)
        out = "{}+{:#x}".format(out, self.offset)
        return out

class Target(object):
    '''
    A wrapper for a Linux GDB Inferior. Includes of various convenience
    methods used for classification.

    WARNING: Methods in this object may change the state of GDB. For
    example, the disassembly flavor may be left as "intel"
    after this code is executed.
    '''
    _re_info_frame = re.compile(r"""^\s*eip\s=\s([^\s;]*)(?:\sin\s)? # addr
                                                ([^\s;]*) # fname
                                                ([^\s;]*) # source_file:line
                                 """, re.VERBOSE)
    _re_gdb_info_sym = re.compile(r"""^\s*(?P<sym>.*?)\s+\+\s+(?P<off>[0-9]+)\s+
                                       in\s+section\s+\.text(\s+
                                       of\s+(?P<lib>.*?)\s*)?$""", re.VERBOSE)
    _re_gdb_addr_bit = re.compile(r"^gdbarch_dump: addr_bit = ([0-9]+)$", re.MULTILINE)
    _re_gdb_osabi = re.compile(r"\(\w+ \"(.*)\"\)")
    _re_gdb_arch = re.compile(r"\(\w+\s+\"*(.+?)\"*\)")

    # these functions and libs are not considered to be at fault for a crash
    blacklist = AttrDict(functions=("__kernel_vsyscall", "abort", "raise",
                                    "malloc", "free", "*__GI_abort",
                                    "*__GI_raise", "malloc_printerr",
                                    "__libc_message", "_int_malloc",
                                    "_int_free"),
                         map_regex=re.compile(r".*/libc(\.|-).*|.*/libm(\.|-).*"))

    def __init__(self, bt_limit=0):
        self._check_inferior_state()
        self.bt_limit = bt_limit

    def _check_inferior_state(self):
        if len(gdb.inferiors()) != 1:
            raise GdbWrapperError("Unsupported number of inferiors ({})".format(len(gdb.inferiors())))
        if len(gdb.inferiors()[0].threads()) == 0:
            raise GdbWrapperError("No threads running")
        if not gdb.inferiors()[0].threads()[0].is_stopped:
            raise GdbWrapperError("Inferior's primary thread is not stopped")

    @memoized
    def backtrace(self):
        return Backtrace(self, self.blacklist, limit=self.bt_limit)

    def hash(self):
        return self.backtrace().hash

    @memoized
    def procmaps(self):
        return ProcMaps()

    @memoized
    def faulting_frame(self):
        for frame in self.backtrace():
            if not frame.blacklisted:
                return frame
        warnings.warn("All frames blacklisted")
        return self.backtrace()[0]

    @staticmethod
    def sym_addr(sym):
        try:
            return gdb_uint(gdb.parse_and_eval(str(sym)))
        except gdb.error:
            return None

    @memoized
    def current_instruction(self):
        try:
            gdbstr = gdb.execute("x/i 0x%x" % self.pc(), False, True).splitlines()[0]
            return self._getInstruction(gdbstr)
        except RuntimeError:
            return None

    def _getInstruction(self, gdbstr):
        return x86Instruction(gdbstr)

    @memoized
    def pc(self):
        return gdb_uint(gdb.parse_and_eval("$pc"))

    @memoized
    def stack_pointer(self):
        return gdb_uint(gdb.parse_and_eval("$sp"))

    @memoized
    def pid(self):
        return gdb.inferiors()[0].pid

    @memoized
    def pointer_size(self):
        return int(self._re_gdb_addr_bit.search(
                       gdb.execute("maint print architecture", False, True)).group(1)) / 8

    @memoized
    def si_signo(self):
        # This is a workaround to a bug in the GDB Python API:
        # The only reliable way to cause GDB to raise an exception when
        # $_siginfo is not available it to call __str__() -- otherwise
        # (such as when casting the Gdb.Value to another type), GDB may
        # force Python to abruptly exit rather than raising an exception
        signo = gdb.parse_and_eval("$_siginfo.si_signo")
        str(signo)
        return signo

    @memoized
    def si_addr(self):
        str(gdb.parse_and_eval("$_siginfo._sifields._sigfault.si_addr"))
        return gdb_uint(gdb.parse_and_eval(
            "$_siginfo._sifields._sigfault.si_addr"))

class x86Target(Target):
    '''
    A wrapper for an x86 Linux GDB Inferior.
    '''

    def __init__(self, bt_limit=0):
        Target.__init__(self, bt_limit)
        self._check_inferior_state()
        gdb.execute("set disassembly-flavor intel", False, True)
