Recursive Process Mapper

README.md

Recursive Process Mapper

This is my take on the recursive process mapper. I followed the hints you gave me about recursion and going in reverse and ended up with a recursive method that:

1. Finds the bottom-most processes as well as any top level processes that don't have any children and turns those into a hierarchy hash of process arrays grouped by parent_pid
2. Removes any processes that were added to the hierarchy hash from the process list
3. Scans the updated process list for any processes that have a pid matching the parent_pid keys in the hierarchy hash. If any are found, it inserts those processes into the hash under a key for their parent_pid, then moves the old child process tuples to be nested under the new parent processes in hierarchy
4. Resolves any circular depencies if detected
5. Repeats steps 2 - 4 until the process list is empty
6. Recursively iterates through the hierarchy to print the nested process info

If I was going to take this further (i.e. get it ready for production):

• Ask for feedback
• There's certainly more that could be DRYed up
• I did test it with multiple circular dependencies, with all of the test data combined, and with some other contrived scenarios, but there are likely other edge cases worth considering
• Write proper tests 🎉
• Run benchmarks on large data sets
• Verify that the procs in the log files are not guaranteed to be in spawn order, which I am pretty sure we confirmed at the beginning of the exercise. This could be made much more simple if that were guaranteed.

But it's 1am on Friday night/Saturday morning and I'm calling it 🙃

output.txt

$ ruby recursive_process_mapper.rb

############################
Test data 1
############################
PID 1416 - winlogon.exe
    PID 11900 - C:\Windows\system32\userinit.exe
        PID 11656 - C:\Windows\Explorer.EXE
            PID 23292 - "rundll32.exe" shell32.dll,OpenAs_RunDLL C:\Users\Bob\AppData\Local\Temp\8e25337b-a52f-4daa-ba4e-e25137403271_download (2).zip.271\Exhibit 1.msg


############################
Test data 2
############################
PID 796 - services.exe
    PID 87228 - "service.exe"
PID 812 - services.exe
    PID 2348 - "service.exe"


############################
Test data 3
############################
PID 59122 - /usr/local/bin/launchd
    PID 50141 - /bin/sh
        PID 71509 - zsh

recursive_process_mapper.rb

# frozen_string_literal: true

require "json"

module RecursiveProcessMapper
  extend self
  
  # Step 1. Find the bottom-most processes as well as any top level processes that don't have any children and turn those into a hierarchy hash of process arrays grouped by parent pid
  # Step 2. Remove any processes moved to the hierarchy from the list of processes
  # Step 3. Search updated process list for any processes that have a pid matching the keys in the hierarchy hash. 
  #         If found, insert those processes into the hash under a key for _their_ parent pids, then move the old tuple so the children are nested under their parent process
  # Step 4. Resolve any circular depencies if detected by promoting the first process in the list to a top-level process, then find the new bottom-most process and inserting it into the hierarchy hash
  # Step 5. Repeat steps 2 - 4 until the process list is empty
  # Step 6. Recursively iterate through the hierarchy to print the nested process info
  def print_process_hierarchy(processes, hierarchy = {})
    if processes.any?
      # Process
      pids_to_delete = []
      if hierarchy.empty?
        # Start with bottom-most procs and childless top level procs
        find_initial_processes(processes).each do |proc|
          hierarchy[proc["parent_pid"].to_i] ||= []
          hierarchy[proc["parent_pid"].to_i] << proc
          pids_to_delete << proc["pid"]
        end
      else
        # Scan next bottom-most procs and nest child procs under them
        parent_pids = hierarchy.keys
        processes.each do |proc|
          next unless parent_pids.include?(proc["pid"])

          pids_to_delete << proc["pid"]
          hierarchy[proc["parent_pid"].to_i] ||= []
          hierarchy[proc["parent_pid"].to_i] << proc.merge("child_processes" => hierarchy.delete(proc["pid"]))
        end
      end

      if pids_to_delete.any?
        # Remove inserted procs
        processes.delete_if { |proc| pids_to_delete.include?(proc["pid"]) }
      else
        # We have a circular dependency to resolve
        resolve_circular_dependency!(processes, hierarchy)
      end

      # Recurse
      print_process_hierarchy(processes, hierarchy)
    else
      # Print results
      if hierarchy.any?
        # Start with our top level procs, both childless and not. We can ignore the parent_pid keys.
        hierarchy.values.flatten.each { |proc| print_proc(proc, 0) }
      else
        raise "No processes were mapped!"
      end
    end
  end

  private

  # Print out nested process threads
  def print_proc(proc, level)
    prefix = "    " * level
    puts "#{prefix}PID #{proc["pid"]} - #{proc["command"]}"

    if proc["child_processes"]
      # Recursively print any child processes
      proc["child_processes"].each do |child_proc|
        print_proc(child_proc, level + 1)
      end
    end
  end

  # Resolve circular dependencies
  def resolve_circular_dependency!(processes, hierarchy)
    # Promote first process to a top level process by unsetting its parent_pid
    processes[0]["parent_pid"] = nil

    # Find the new bottom most process(es) and insert them into the hierarchy
    pids_to_delete = []
    find_initial_processes(processes).each do |proc|
      hierarchy[proc["parent_pid"]] ||= []
      hierarchy[proc["parent_pid"]] << proc
      pids_to_delete << proc["pid"]
    end

    if pids_to_delete.any?
      # Remove inserted processes
      processes.delete_if { |proc| pids_to_delete.include?(proc["pid"]) }
    else
      raise "Could not resolve circular dependency!"
    end
  end

  # Find bottom-most and childless top-most processes
  def find_initial_processes(processes)
    known_pids = []
    known_parent_pids = []
    processes.each do |proc|
      known_pids << proc["pid"]
      known_parent_pids << proc["parent_pid"] unless proc["parent_pid"].nil?
    end

    processes.select do |proc|
      is_bottom_level_proc?(proc, known_pids:, known_parent_pids:) || is_childless_top_level_proc?(proc, known_pids:, known_parent_pids:)
    end
  end

  # Identifies childless procs
  # Childless procs are procs whose pids are not in the list of known parent_pids
  def is_childless_proc?(proc, known_parent_pids:)
    !known_parent_pids.include?(proc["pid"])
  end

  # Identifies bottom level procs
  # Bottom-level procs are childless procs whose parent_pid is in the list of known pids
  def is_bottom_level_proc?(proc, known_pids:, known_parent_pids:)
    known_pids.include?(proc["parent_pid"]) &&
      is_childless_proc?(proc, known_parent_pids:)
  end

  # Identifies top level procs
  # Top level procs are procs that do not have a parent_pid OR whose parent_pid is not in the list of known pids
  def is_top_level_proc?(proc, known_pids:)
    proc["parent_pid"].nil? || !known_pids.include?(proc["parent_pid"])
  end

  # Identifies childless top level procs
  def is_childless_top_level_proc?(proc, known_pids:, known_parent_pids:)
    is_top_level_proc?(proc, known_pids:) && is_childless_proc?(proc, known_parent_pids:)
  end
end

test_data1 = <<~'JSON'
  [
    {
      "pid": 1416,
      "parent_pid": null,
      "command": "winlogon.exe"
    },
    {
      "pid": 11900,
      "parent_pid": 1416,
      "command": "C:\\Windows\\system32\\userinit.exe"
    },
    {
      "pid": 11656,
      "parent_pid": 11900,
      "command": "C:\\Windows\\Explorer.EXE"
    },
    {
      "pid": 23292,
      "parent_pid": 11656,
      "command": "\"rundll32.exe\" shell32.dll,OpenAs_RunDLL C:\\Users\\Bob\\AppData\\Local\\Temp\\8e25337b-a52f-4daa-ba4e-e25137403271_download (2).zip.271\\Exhibit 1.msg"
    }
  ]
JSON
# ############################
# Test data 1 expected output:
# ############################
# PID 1416 - winlogon.exe
#     PID 11900 - C:\Windows\system32\userinit.exe
#         PID 11656 - C:\Windows\Explorer.EXE
#             PID 23292 - "rundll32.exe" shell32.dll,OpenAs_RunDLL C:\Users\Bob\AppData\Local\Temp\8e25337b-a52f-4daa-ba4e-e25137403271_download (2).zip.271\Exhibit 1.msg
puts "############################"
puts "Test data 1"
puts "############################"
RecursiveProcessMapper.print_process_hierarchy(JSON.parse(test_data1))

test_data2 = <<~'JSON'
  [
    {
      "pid": 796,
      "parent_pid": 668,
      "command": "services.exe"
    },
    {
      "pid": 87228,
      "parent_pid": 796,
      "command": "\"service.exe\""
    },
    {
      "pid": 812,
      "parent_pid": 724,
      "command": "services.exe"
    },
    {
      "pid": 2348,
      "parent_pid": 812,
      "command": "\"service.exe\""
    }
  ]
JSON
# ############################
# Test data 2 expected output:
# ############################
# PID 796 - services.exe
#     PID 87228 - "service.exe"
# PID 812 - services.exe
#     PID 2348 - "service.exe"
puts "\n\n############################"
puts "Test data 2"
puts "############################"
RecursiveProcessMapper.print_process_hierarchy(JSON.parse(test_data2))

test_data3 = <<~'JSON'
  [
    {
      "pid": 59122,
      "parent_pid": 71509,
      "command": "/usr/local/bin/launchd"
    },
    {
      "pid": 71509,
      "parent_pid": 50141,
      "command": "zsh"
    },
    {
      "pid": 50141,
      "parent_pid": 59122,
      "command": "/bin/sh"
    }
  ]
JSON
# ############################
# Test data 3 expected output:
# ############################
# PID 59122 - /usr/local/bin/launchd
#     PID 50141 - /bin/sh
#         PID 71509 - zsh
puts "\n\n############################"
puts "Test data 3"
puts "############################"
RecursiveProcessMapper.print_process_hierarchy(JSON.parse(test_data3))