Transcript OSPF Validation

OSPF Validation
Dirk Jacob
[email protected]
http://ssfnet.d-jacob.net
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 2
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 3
SSFNet - Overview
 Simulation of very large networks
 Focus on scalability
 modeling scalability
 computing scalability
 Layered Architecture
Dirk Jacob, Page 4
Scalable Simulation
Framework
 Simulator Kernel – not dedicated to simulation of networks
 „Models“ are built on top of the SSF API
 consists of only five core classes:
Entity, Event, inChannel, outChannel and process
 API hides all simulator internals
 C++ and Java bindings
 models are standard programs which extend the standard SSF classes
 Different SSF implementations available
Dirk Jacob, Page 5
SSF Network Models
 Set of SSF Java models, which simulate the networking world
 distributed under the GPL
 consists of several sub-packages
 SSF.OS
Framework for protocol modeling
 SSF.Net
models for hardware components
 SSF.Util.Random
generation of multiple independent random number streams
 SSF.Util.Streams
efficient multi-point monitoring infrastructure
Dirk Jacob, Page 6
SSF.OS
 Framework for modeling of protocols
 three classes:
 ProtocolSession,
 ProtocolMessage,
 ProtocolGraph
 Packets are modeled by ProtocolMessages
Dirk Jacob, Page 7
SSFNet Protocols
 SSFNet comes with a variety of protocols
 IP
 UDP
 TCP
 Sockets
 HTTP
 BGP
 „Static“ OSPF
 OSPFv2
Dirk Jacob, Page 8
SSF.Net
 Models for the simulation of networking components
 Networks
 Hosts
 Routers
 Links
 Network Interfaces (NIC)
 additional Classes like packet queues, routing tables, etc.
Dirk Jacob, Page 9
Modeling Topologies
 Topologies are modeled using DML
 consists of nested key/value pairs
 supports attribute substitution
 supports inheritance
 component configurations can be kept in a dictionary for reuse
 Example
dict [
myrouter [
interface [ id 0
_extends .dict.if100Mbit]
graph [
ProtocolSession[name ip
use SSF.OS.IP]
ProtocolSession[name ospf
use SSF.OS.OSPF.sOSPF]
]
]
]
Net [
router[ id
_extends
router[ id
_extends
1
.dict.myrouter ]
2
.dict.myrouter ]
link[ attach 1(0) attach 2(0) ]
]
Dirk Jacob, Page 10
Role of Testing
 Protocols must be implemented correctly
 Conformance tests to prove conformance with standards
 Regression tests to verify that things still work after changes
 Testing is extremely important!
Dirk Jacob, Page 11
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 12
Categories of Testing
 Conformance testing
 Regression testing
 Performance testing
 Stress testing
 Roustness tests
 Here: focus on conformance testing
Dirk Jacob, Page 13
Conformance Testing
 Verify that a protocol implementation performs as required
in the standard
 Black box testing: observe outputs, when IUT is feeded with
various inputs
 Exhaustive testing: apply every possible input sequence
 not possible with complex protocols
 Test only important input sequences
 Main problem: identify important input sequences
Dirk Jacob, Page 14
OSI Testing Methodology
 Framework for conformance testing of OSI protocols
 Standardized in ISO 9646
 based on the OSI Reference Model
 Standardized test procedure
Dirk Jacob, Page 15
Test Architectures
Local Method
Distributed Method
Dirk Jacob, Page 16
Test Architectures (2)
Coordinated Method
Remote Method
Dirk Jacob, Page 17
TTCN
 standardized notation for the description of test cases
 event trees, which describe the external behavior of a protocol
 two forms: TTCN/gr and TTCN/mp
 four parts
 overview part
 declarations part
 constraints part
 dynamic part
LT!SYN_Packet
START wait_timer
LT?ACK_Packet
LT!FIN_Packet
TIMEOUT wait_timer
LT!FIN_acket
Example for dynamic part
Dirk Jacob, Page 18
Test Case Selection
 not specified in OSI framework
 but: central role for coverage and correctness of test suite
 efforts to use formal techniques
 provable correctess
 provable coverage
Dirk Jacob, Page 19
Test Selection based on
FSMs
 several methods for test case selection based on FSMs
 transition tours
 distinguishing sequences
 characterizing sequences (W-Method)
 unique I/O sequences
 apply an input sequence which must produce
a specific output sequence
 protocol must be specified as an FSM
 restrictions
 strongly connected
 fully specified
 not applicable to most complex protocols
Dirk Jacob, Page 20
Formal Description
Techniques
 data portion of protocols often are not specified as FSM
 FDTs are formal languages for specification
 SDL
 MSC
 LOTOS
 Estelle
 specifications can be represented as labelled transition systems
 similar to FSMs
 different methods/algorithms for derivation of test cases from LTS
Dirk Jacob, Page 21
Informal Testing
 many protocols are specified using natural language
 translating them into a FDT may cause errors
 test cases may not reflect the standard
 many formal methods cannot be applied to complex protocols
 often informal methods are used
 reading the standard and deriving tests directly
 no provable correctness and coverage
 but: „high degree of certainty“
Dirk Jacob, Page 22
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 23
OSPF Overview
 Link-state intra-domain routing protocol
 OSPF Router knows the whole topology of the network
 Specified in RFC 2328
 Routing Information is exchanged with directly attached neighors
 flooding procedure assures distribution over the whole network
 Hierarchical Concept
 support for large networks
 reduce CPU and memory requirements
 Support for multiple least cost routes to the same destination
 Uses Dijkstra‘s SPF algorithm to calculate routing tables
Dirk Jacob, Page 24
OSPF Overview (2)
 Routers identify their neighbors
 Some neighbors form adjacencies in order to exchange
routing information
 Synchronization through the exchange of link state databases
 Detect link failures through periodic sending/receiving of
Hello Packets
 Changes in the topology are flooded as Link State Updates
 All information is re-flooded periodically to keep databases
consistent
 OSPF distinguishes different network types:
broadcast, nonboadcast-multiaccess (NBMA), point-to-point and point-to-multipoint
Dirk Jacob, Page 25
Hierarchical Routing
 each AS can be divided into Areas
 each area has ist own Link State Database
 detailed information of area topology only known inside the area
 information about area is summarized into other areas
 special backbone area (area 0)
 all areas must be connected to the
backbone
 virtual links to connect areas
to the backbone which have no
physical connection
 Stub areas to reduce database
sizes
Dirk Jacob, Page 26
Link State Database
 Contains information about area topology
 Describes a graph
 Routers and networks are vertices
 Links between vertices are edges
 Links are asociated with a cost/metric
 Network vertices are represented by a designated router
Dirk Jacob, Page 27
Functional Areas
 4 mostly independent functional areas
 detection and maintenance of neighbors
 building adjacencies
 the flooding procedure
 routing table calculation
Dirk Jacob, Page 28
Neighbor Discovery and
Maintenance
 Send Hello Packets periodically
 Include information about neighbors
 Assure bi-directional communication
 Assure that neighbors agree on certain parameters
 Elect Designated Router on broadcast and NBMA networks
 Represent the network in
the Link State Database
 reduce the number of
adjacencies
Dirk Jacob, Page 29
Building Adjacencies
 neighbors with bi-directional communication become adjacent
 dependent of network type
 Synchronization of Link State Databases
 Negotiate, who is the master in this process
 Master controls the exchange process
 Send summary of own Database in Database Description Packets
 Request unknown or more recent LSAs from the neighbor
 Send requested LSAs to the neighbor
Dirk Jacob, Page 30
Reliable Flooding
 Each router must keep synchronized with every other router in
the same area
 Udates are flooded to all adjacent neighbors
 Every Update must be acknowledged
 Explicitly through an Ack packet
 Implicitly with an Update of the same LSA flooded back
 Retransmit Update if there is no such acknowledgement
 Possibility of delayed Acks to minimize number of packets
Dirk Jacob, Page 31
Link State Advertisements
 different types of LSAs
 Router LSAs – represent a router with all its associated links
 Network LSAs – represent broadcast and NBMA networks
 Network Summary LSAs – represent routes to destinations in other areas
 ASBR Summary LSAs – represent routes to AS boundary routers
 AS-external LSAs – represent routes to AS external destinations
 LSAs have an age associated with them
 aging in databases and during the flooding procedure
 premature aging to remove LSAs from databases
 don‘t use LSAs that are older than 1 hour for routing calculation
 refresh own LSAs that are older than ½ hour
 use of sequence numbers to determine, which instance of an
LSA is the most recent one
Dirk Jacob, Page 32
Routing Table Calculation
 Dijkstra‘s Shortest Path First algorithm
 Calculate SPF tree for the area using the SPF algorithm
 Consider only routers and network nodes from the LSDB
 Add stub networks to the tree
 Add inter-area routes to the tree
 Examine summary LSAs to find better routes for destinations
in areas connected through virtual links
 Add AS external routes to the tree
Dirk Jacob, Page 33
Testing OSPF
 take advantage from the functional structure
 four smaller testing problems instead of a big one
 each functional area can be tested independently
 take care of dependencies
 functional hierarchy rather than completely independent
areas
 test „lower level“ functionality first
Dirk Jacob, Page 34
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 35
OSPF Test Suites
 most of the formal methods require protocol specification
with FSMs
 OSPF only partially specified by FSMs
 many parts like LSA origination not covered
 most parts are specified using natural language
 OSPF consists of multiple concurrent processes
 Formal methods require formal specifications
 not provided for OSPF, must be derived manually from standard
 Formal methods difficult to apply to OSPF
Dirk Jacob, Page 36
C-TTCN Based Test Suite
 approach to testing OSPF with formal methods
 modeling test cases with C-TTCN
 extension to TTCN which allows modeling of concurrent behaviors
 OSPF specification was translated into a FDT called CEBE
 based on LTS, which are similar to FSMs
 resulting test suite had over 4000 test cases
 after elimination of unimportant test cases: 543 test cases
 Problem: how to prove that formal specification covers the
complete OSPF specification?
Dirk Jacob, Page 37
IOL Test Suite
 IOL is a test lab, whose services are used by many vendors
 Test suites are derived by „carefully reading the standards“
 good coverage and correctness
 used by many vendors
 refined over the time
 covers the functional areas of OSPF presented before
 Hello Protocol tests
 Fooding and Adjacency tests
 Link state advertisement tests
 Route calculation tests
 Additionally: Configuration and Formatting tests
 78 test cases with several test steps each
Dirk Jacob, Page 38
Commecial Test Products
 ANVL
 software solution for conformance and performance testing
 used by many well-known vendors
 provides automated testing
 OSPF test suite consists of over 300 test cases from 12 groups
 no formal methods are used
 QARobot / RouterTester
 hardware solution together with protocol and test suite software
 conformance and stress testing
 OSPF test sute has 70 test cases from 12 groups
 no formal methods are used
Dirk Jacob, Page 39
Testing OSPF in Practice
 in practice: mixture of several different test products and/or
lab testing
 Example: ZebOS Advanced Routing Suite
 basic testing with ANVL
 additionally performance testing using other test tools
 after that: lab testing at the IOL and other labs
 Testing against multiple test suites increases probability of
finding any offences against the specification
Dirk Jacob, Page 40
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 41
OSPF Test Suite for SSFNet
 OSI methods can be easily transferred into SSFNet
 Test Procedure needs not to be modified
 Extended test architecture to support distributed test behavior
 Test cases can be modeled using appropriate DML scenarios
 some test cases need implementation of specialized testers
Dirk Jacob, Page 42
SSF.OS.OSPFv2
 Goal: implement a complete OSPF for SSFNet
 Must correctly implement the standard
 until now:
 Hello Protocol, Database Exchange, Flooding and Routing Table Calculation
 only Router LSAs
 restricted to point-to-point networks
 no vitual links or authentication
 work still in progress
Dirk Jacob, Page 43
Test Selection
 depends on several criteria
 correctness
 coverage
 relevance and acceptance in practice
 ease of implementation
 applicability early during development
 availability
 formal methods are difficult to apply and not very common
 dedicated test equipment not applicable easily
 software solution like ANVL also not applicable
 IOL test suite seems the best choice
Dirk Jacob, Page 44
Design of the Test Suite
 many tests can be implemented using standard OSPF behavior
 some require specialized testers with non-standard behavior
 topology changes such as link failures
 simple errors like malformed packets
 complex tests which are aware of the state
 test behaviors are implemented in SSF.OS.OSPFv2.test
 five subsidiary test suites (see IOL test suite)
 additionally: tests for packet forwarding and equal-cost multipath
Dirk Jacob, Page 45
Design of the Test Suite (2)
 each test is performed in several steps
 simulation of the scenario
 evaluation of the logs
 assignment of a verdict
 evaluation is done automatically by PERL scripts
 verdicts: PASS, FAIL or INCONCLUSIVE
 test suite passes only when all tests pass
 common components for simulation are kept in a test suite
dictionary
Dirk Jacob, Page 46
SSF.OS.OSPFv2.test
 contains classes to implement test behavior
 Configurator
 Reset
 UnreliableIP
 IPwithErrorInjection
 PacketGenerator
 OSPFMonitor, OSPFDumpPro
 main task: manipulate packets coming from or sent to OSPF
Dirk Jacob, Page 47
SSF.OS.OSPFv2.test (2)
 class hierarchy to be able to use different classes of testers
together
Dirk Jacob, Page 48
Implementation of Test
Cases
 model test setup in DML
 replace broadcast networks by a set of point-to-point links
 features specific to broadcast networks, virtual links, etc.
not yet tested
 use tester classes to model tester behavior whenever necessary
Dirk Jacob, Page 49
Example: old_lsa_rcpt
• a router must discard an LSA
that is older than the copy in ist
own database
IUT
Tester
• routers synchronize their databases
• then the tester sends a new LSA with sequence no. 0x70000001
• after that, it sends another LSA with sequence no. 0x 8FFFFFFE
• IUT must send back the newer instance and discard
the second LSA
Dirk Jacob, Page 50
Additional Tests
 operation of the SPF algorithm not tested by IOL test suite
 packet forwarding and support of equal-cost multiplath not
tested in IOL test suite
 provide additional test scenarios for these features
Dirk Jacob, Page 51
Test Results
 most tests PASSED
 some of the tests FAILED because of features missing from
SSFnet (esp. multicast support)
 many tests INCONCLUSIVE, because features are not yet
implemented
 tests were very valuable during development
 helped identifying problems early
 helped make code more stable
 helped to find even „standard bugs“ like NullPointerExceptions
Dirk Jacob, Page 52
Overview
SSFNet
Conformance Testing
OSPF
OSPF Test Suites
Implementation for SSFNet
Summary
Dirk Jacob, Page 53
Summary
 goals:
 find out how to test protocols
 provide SSFNet with a test suite for OSPF
 formal methods seem not suitale for practical testing
 informal methods sufficient when used carefully
 formal methods could have grater impact if test suites were provided with
the protocol standards
 testing is extremely important and useful
 to prove cnformance to the standard (at least to some degree)
 to find bugs in the implementation
 to understand, what a protocol really should do
Dirk Jacob, Page 54
Questions?
 OSPF validation in SSFNet:
 http://ssfnet.d-jacob.net
 SSFNet Website:
 http://www.ssfnet.org
 Test equipment and test suites:
 http://www.agilent.com
 http://www.ixia.com
 http://www.iol.unh.edu
 ... or send me a mail:
 [email protected]
Dirk Jacob, Page 55
END.
Dirk Jacob, Page 56