control_flow Package

control_flow Package

base Module

class sts.control_flow.base.ControlFlow(simulation_cfg)

Bases: object

Superclass of ControlFlow types

__init__(simulation_cfg)

get_sync_callback()

init_results(results_dir)

Set up event log files

simulate()

Move the simulation forward!

class sts.control_flow.base.RecordingSyncCallback(input_logger, record_deterministic_values=False)

Bases: sts.syncproto.sts_syncer.STSSyncCallback

__init__(input_logger, record_deterministic_values=False)

get_deterministic_value(controller, name, xid)

state_change(sync_type, xid, controller, time, fingerprint, name, value)

class sts.control_flow.base.ReplaySyncCallback(get_interpolated_time=None)

Bases: sts.syncproto.sts_syncer.STSSyncCallback, pox.lib.revent.revent.EventMixin

__init__(get_interpolated_time=None)

If get_interpolated_time is None, will always wait on deterministic values. If not None, will always invoke get_interpolated_time and respond immediately

ack_pending_state_change(pending_state_change)

ACK the pending state change, and collect the PendingStateChange from our buffer

flush()

ACK any pending state changes

get_deterministic_value(controller, name, xid)

pending_deterministic_value_request(controller_id)

pending_state_changes()

Return any pending state changes

pending_state_changes_with_counts()

Return any pending state changes

send_deterministic_value(controller_id, value)

set_pass_through()

Cause all pending state changes to pass through without being buffered

state_change(sync_type, xid, controller, time, fingerprint, name, value)

state_change_pending(pending_state_change)

Return whether the PendingStateChange has been observed

unset_pass_through()

Unset pass through mode, and return any events that were passed through since pass through mode was set

class sts.control_flow.base.StateChange(pending_state_change)

Bases: pox.lib.revent.revent.Event

__init__(pending_state_change)

event_scheduler Module

class sts.control_flow.event_scheduler.DumbEventScheduler(simulation, epsilon_seconds=0.0, sleep_interval_seconds=0.2)

Bases: sts.control_flow.event_scheduler.EventSchedulerBase

__init__(simulation, epsilon_seconds=0.0, sleep_interval_seconds=0.2)

kwargs = set(['epsilon_seconds', 'sleep_interval_seconds'])

schedule(event)

class sts.control_flow.event_scheduler.EventScheduler(simulation, speedup=1.0, delay_input_events=True, initial_wait=0.5, epsilon_seconds=0.5, sleep_interval_seconds=0.2)

Bases: sts.control_flow.event_scheduler.EventSchedulerBase

an EventWatchers schedules events. It controls their admission, and any post-event delay

__init__(simulation, speedup=1.0, delay_input_events=True, initial_wait=0.5, epsilon_seconds=0.5, sleep_interval_seconds=0.2)

inject_input(event)

kwargs = set(['initial_wait', 'delay_input_events', 'epsilon_seconds', 'speedup', 'sleep_interval_seconds'])

schedule(event)

update_event_time(event)

update our bearing on where we currently our in the timeline

wait_for_internal(event)

wait_time(event)

returns how long to wait in seconds for an event to occur or be injected.

class sts.control_flow.event_scheduler.EventSchedulerBase

Bases: object

__init__()

set_input_logger(input_logger)

class sts.control_flow.event_scheduler.EventSchedulerStats

Bases: object

__init__()

event_matched(event)

event_timed_out(event)

sorted_match_counts()

sorted_timeout_counts()

start_replay(event)

time(event)

sts.control_flow.event_scheduler.format_time(time)

fuzzer Module

Three control flow types for running the simulation forward.

• Fuzzer: injects input events at random intervals, periodically checking for invariant violations
• Interactive: presents an interactive prompt for injecting events and checking for invariants at the users’ discretion

class sts.control_flow.fuzzer.Fuzzer(simulation_cfg, fuzzer_params='config.fuzzer_params', check_interval=None, traffic_inject_interval=10, random_seed=None, delay=0.1, steps=None, input_logger=None, invariant_check_name='InvariantChecker.check_correspondence', halt_on_violation=False, log_invariant_checks=True, delay_startup=True, print_buffers=True, record_deterministic_values=False, mock_link_discovery=False, initialization_rounds=0)

Bases: sts.control_flow.base.ControlFlow

Injects input events at random intervals, periodically checking for invariant violations. (Not the proper use of the term Fuzzer)

__init__(simulation_cfg, fuzzer_params='config.fuzzer_params', check_interval=None, traffic_inject_interval=10, random_seed=None, delay=0.1, steps=None, input_logger=None, invariant_check_name='InvariantChecker.check_correspondence', halt_on_violation=False, log_invariant_checks=True, delay_startup=True, print_buffers=True, record_deterministic_values=False, mock_link_discovery=False, initialization_rounds=0)

Options:

• fuzzer_params: path to event probabilities
• check_interval: the period for checking invariants, in terms of logical rounds
• traffic_inject_interval: how often to inject dataplane trace packets
• random_seed: optionally set the seed of the random number generator
• delay: how long to sleep between each logical round
• input_logger: None, or a InputLogger instance
• invariant_check_name: the name of the invariant check, from config/invariant_checks.py
• halt_on_violation: whether to stop after a bug has been detected
• log_invariant_checks: whether to log InvariantCheck events
• delay_startup: whether to until the first OpenFlow message is received before proceeding with fuzzing
• print_buffers: whether to print the remaining contents of the dataplane/controlplane buffers at the end of the execution
• record_deterministic_values: whether to record gettimeofday requests for replay
• mock_link_discovery: optional module for POX to experiment with better determinism – tell POX exactly when links should be discovered
• initialization_rounds: if non-zero, will wait the specified rounds to let the controller discover the topology before injecting inputs

check_controllers()

check_dataplane(pass_through=False)

Decide whether to delay, drop, or deliver packets

check_link_failures()

check_migrations()

check_pending_messages(pass_through=False)

check_switch_crashes()

Decide whether to crash or restart switches, links and controllers

check_tcp_connections()

Decide whether to block or unblock control channels

fuzz_traffic()

init_results(results_dir)

loop()

maybe_check_invariant()

maybe_inject_trace_event()

simulate()

Precondition: simulation.patch_panel is a buffered patch panel

trigger_events()

interactive Module

control flow type for running the simulation forward.

• Interactive: presents an interactive prompt for injecting events and checking for invariants at the users’ discretion

class sts.control_flow.interactive.Interactive(simulation_cfg, input_logger=None)

Bases: sts.control_flow.base.ControlFlow

Presents an interactive prompt for injecting events and checking for invariants at the users’ discretion

__init__(simulation_cfg, input_logger=None)

cut_link(dpid1, dpid2)

dataplane_delay(event=None)

dataplane_drop(event=None)

dataplane_forward(event=None)

dataplane_trace_feed()

default_command()

init_results(results_dir)

invariant_check(kind)

kill_controller(label)

kill_switch(dpid)

list_controllers()

list_hosts()

list_switches()

migrate_host(hid, dpid)

next_step()

quit()

repair_link(dpid1, dpid2)

show_flow_table(dpid)

show_queued_events()

simulate(simulation=None, bound_objects=())

start_controller(label)

start_switch(dpid)

class sts.control_flow.interactive.STSCommand(func, name, alias, help_msg)

Bases: object

__init__(func, name, alias, help_msg)

arg(name, help_msg=None, values=None)

arg_help()

get_help()

class sts.control_flow.interactive.STSCommandArg(name, help_msg=None, values=None)

Bases: object

__init__(name, help_msg=None, values=None)

arg_help()

values()

class sts.control_flow.interactive.STSConsole(default_command=None)

Bases: object

__init__(default_command=None)

autocomplete_matches(text, index)

cmd(func, name, alias=None, help_msg=None)

cmd_group(name)

default_command

register_obj(obj, name, alias=None, help_msg=None)

run()

show_help(command=None)

class sts.control_flow.interactive.STSRegisteredObject(obj, name, alias, help_msg)

Bases: object

__init__(obj, name, alias, help_msg)

get_help()

mcs_finder Module

An orchestrating control flow that invokes replayer several times to find the minimal causal sequence (MCS) of a failure.

class sts.control_flow.mcs_finder.EfficientMCSFinder(simulation_cfg, superlog_path_or_dag, invariant_check_name=None, transform_dag=None, end_wait_seconds=0.5, mcs_trace_path=None, extra_log=None, runtime_stats_file=None, wait_on_deterministic_values=False, no_violation_verification_runs=1, optimized_filtering=False, forker=<sts.util.rpc_forker.LocalForker object at 0x59ce610>, replay_final_trace=False, **kwargs)

Bases: sts.control_flow.mcs_finder.MCSFinder

Exactly the same functionality as MCSFinder, but assumes that indeterminate results cannot occur. Worst-case runtime of O(n) as opposed to O(n^2) replays. Taken from the predecessor paper:

http://www.st.cs.uni-saarland.de/publications/files/zeller-esec-1999.pdf

Section 4

class sts.control_flow.mcs_finder.MCSFinder(simulation_cfg, superlog_path_or_dag, invariant_check_name=None, transform_dag=None, end_wait_seconds=0.5, mcs_trace_path=None, extra_log=None, runtime_stats_file=None, wait_on_deterministic_values=False, no_violation_verification_runs=1, optimized_filtering=False, forker=<sts.util.rpc_forker.LocalForker object at 0x59ce610>, replay_final_trace=False, **kwargs)

Bases: sts.control_flow.base.ControlFlow

__init__(simulation_cfg, superlog_path_or_dag, invariant_check_name=None, transform_dag=None, end_wait_seconds=0.5, mcs_trace_path=None, extra_log=None, runtime_stats_file=None, wait_on_deterministic_values=False, no_violation_verification_runs=1, optimized_filtering=False, forker=<sts.util.rpc_forker.LocalForker object at 0x59ce610>, replay_final_trace=False, **kwargs)

init_results(results_dir)

log(s)

Output a message to both self._log and self._extra_log

log_no_violation(s)

Output a message to both self._log and self._extra_log

log_violation(s)

Output a message to both self._log and self._extra_log

replay(new_dag, label)

simulate(check_reproducability=True)

class sts.control_flow.mcs_finder.MCSLogTracker(results_dir, mcs_trace_path, runtime_stats, simulation_cfg, peeker_exists)

Bases: object

Logs intermedate and final MCS results that are the outcome(s) of delta debugging

__init__(results_dir, mcs_trace_path, runtime_stats, simulation_cfg, peeker_exists)

dump_mcs_trace(dag, control_flow, mcs_trace_path=None)

dump_runtime_stats(runtime_stats_file=None)

maybe_dump_intermediate_mcs(dag, label, control_flow)

class sts.control_flow.mcs_finder.ReplayLogTracker(results_dir)

Bases: object

Logs intermediate and final replay traces chosen by delta debugging

__init__(results_dir)

static create_replay_logger_dir(results_dir)

get_replay_logger_dir(label)

class sts.control_flow.mcs_finder.RuntimeStats(runtime_stats_file)

Bases: object

Tracks statistics and configuration information of the delta debugging runs

__init__(runtime_stats_file)

client_dict()

Return a serializable dict

clone()

merge_client_dict(client_dict)

record_early_internal_events(early_internal_events)

record_global_stats()

record_iteration_size(iteration_size)

record_matched_events(matched_events)

record_new_internal_events(new_internal_events)

record_prune_end()

record_prune_start()

record_replay_end()

record_replay_start()

record_timed_out_events(timed_out_events)

record_violation_found(verification_iteration)

set_config(config)

set_dag_stats(dag)

set_initial_verification_runs_needed(verification_runs)

set_peeker(peeker)

write_runtime_stats()

peeker Module

class sts.control_flow.peeker.Peeker(simulation_cfg, default_wait_time_seconds=0.5, epsilon_time=0.2)

Bases: object

__init__(simulation_cfg, default_wait_time_seconds=0.5, epsilon_time=0.2)

ambiguous_counts = Counter()

ambiguous_events = Counter()

find_internal_events(replay_dag, wait_time_seconds)

Replay the replay_dag, then wait for wait_time_seconds and collect internal events that occur. Return the list of internal events.

get_wait_time_seconds(first_event, second_event)

match_and_filter(newly_inferred_events, expected_internal_events)

peek(dag)

Infer which internal events are/aren’t going to occur,

sts.control_flow.peeker.correct_timestamps(new_events, old_events)

Set new_events’ timestamps to approximately the same timestamp as old_events.

Precondition: old_events != []

sts.control_flow.peeker.count_overlapping_fingerprints(newly_inferred_events, expected_internal_events)

Track # of instances where an expected event matches 2 or more inferred events. Mutates Peeker.ambiguous_counts and Peeker.ambiguous_events

sts.control_flow.peeker.get_expected_internal_events(left_input, right_input, events_list)

Return previously observed internal events between the left_input and the right_input event

left_input may be None case we return events from the beginning of events_list

right_input may also be None, in which case we return all events following left_input

sts.control_flow.peeker.match_fingerprints(newly_inferred_events, expected_internal_events)

replayer Module

control flow for running the simulation forward.

• Replayer: takes as input a superlog with causal dependencies, and iteratively prunes until the MCS has been found

class sts.control_flow.replayer.DataplaneChecker(event_dag, slop_buffer=10)

Bases: object

Dataplane permits are the default, unless they were explicitly dropped in the initial run. This class keeps track of whether pending dataplane events should be dropped or forwarded during replay

__init__(event_dag, slop_buffer=10)

Consider the round i of a DataplaneDrop in the original event ordering. slop_buffer defines how tolerant we are to differences in the position of the correspdonding DataplaneDrop event in the pruned run. A slop_buffer of 4 says that we will tolerate the same DataplaneDrop in the pruned run occuring in the range [i-4,i+4]. If the corresponding DataplaneDrop occurs outside of this window, we won’t detect it, and will treat it as a default DataplanePermit

check_dataplane(current_round, simulation)

Check dataplane events for before playing then next event. - current_event_idx allows us to adjust our current slop buffer

decide_drop(dp_event)

Returns True if this event should be dropped, False otherwise

update_window(current_round)

Update the current slop buffer (“the dp_events we expect to see”)

class sts.control_flow.replayer.DataplaneCheckerStats(events)

Bases: object

Tracks how many drops we actually performed vs. how many we expected to perform

__init__(events)

record_drop(fingerprint)

class sts.control_flow.replayer.Replayer(simulation_cfg, superlog_path_or_dag, create_event_scheduler=None, print_buffers=True, wait_on_deterministic_values=False, default_dp_permit=False, fail_to_interactive=False, input_logger=None, **kwargs)

Bases: sts.control_flow.base.ControlFlow

Replay events from a trace

To set the event scheduling parameters, pass them as keyword args to the constructor of this class, which will pass them on to the EventScheduler object it creates.

__init__(simulation_cfg, superlog_path_or_dag, create_event_scheduler=None, print_buffers=True, wait_on_deterministic_values=False, default_dp_permit=False, fail_to_interactive=False, input_logger=None, **kwargs)

compute_interpolated_time(current_event)

get_interpolated_time()

During divergence, the controller may ask for the current time more or less times than they did in the original run. We control the time, so we need to give them some answer. The answers we give them should be (i) monotonically increasing, and (ii) between the time of the last recorded (“landmark”) event and the next landmark event, and (iii) as close to the recorded times as possible

Our temporary solution is to always return the time right before the next landmark

increment_round()

run_simulation_forward(dag, post_bootstrap_hook=None)

simulate(post_bootstrap_hook=None)

Caller must call simulation.clean_up()

time_epsilon_microseconds = 500

total_inputs_replayed = 0

total_replays = 0