• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/python3
2#
3# Copyright 2017 The Android Open Source Project
4#
5# Licensed under the Apache License, Version 2.0 (the "License");
6# you may not use this file except in compliance with the License.
7# You may obtain a copy of the License at
8#
9# http://www.apache.org/licenses/LICENSE-2.0
10#
11# Unless required by applicable law or agreed to in writing, software
12# distributed under the License is distributed on an "AS IS" BASIS,
13# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14# See the License for the specific language governing permissions and
15# limitations under the License.
16
17import posix
18import select
19from socket import *  # pylint: disable=wildcard-import
20import time
21import unittest
22from math import pow
23
24import multinetwork_base
25
26def accumulate(lis):
27  total = 0
28  for x in lis:
29    total += x
30    yield total
31
32# This test attempts to validate time related behavior of the kernel
33# under test and is therefore inherently prone to races. To avoid
34# flakes, this test is biased to declare RFC 7559 RS backoff is
35# present on the assumption that repeated runs will detect
36# non-compliant kernels with high probability.
37#
38# If higher confidence is required, REQUIRED_SAMPLES and
39# SAMPLE_INTERVAL can be increased at the cost of increased runtime.
40class ResilientRouterSolicitationTest(multinetwork_base.MultiNetworkBaseTest):
41  """Tests for IPv6 'resilient rs' RFC 7559 backoff behaviour.
42
43  Relevant kernel commits:
44    upstream:
45      bd11f0741fa5 ipv6 addrconf: implement RFC7559 router solicitation backoff
46    android-4.4:
47      e246a2f11fcc UPSTREAM: ipv6 addrconf: implement RFC7559 router solicitation backoff
48
49    android-4.1:
50      c6e9a50816a0 UPSTREAM: ipv6 addrconf: implement RFC7559 router solicitation backoff
51
52    android-3.18:
53      2a7561c61417 UPSTREAM: ipv6 addrconf: implement RFC7559 router solicitation backoff
54
55    android-3.10:
56      ce2d59ac01f3 BACKPORT: ipv6 addrconf: implement RFC7559 router solicitation backoff
57
58  """
59  ROUTER_SOLICIT = 133
60
61  _TEST_NETID = 123
62  _PROC_NET_TUNABLE = "/proc/sys/net/ipv6/conf/%s/%s"
63
64  @classmethod
65  def setUpClass(cls):
66    return
67
68  def setUp(self):
69    return
70
71  @classmethod
72  def tearDownClass(cls):
73    return
74
75  def tearDown(self):
76    return
77
78  @classmethod
79  def isIPv6RouterSolicitation(cls, packet):
80    def ToByte(c):
81      return c if isinstance(c, int) else ord(c)
82
83    return ((len(packet) >= 14 + 40 + 1) and
84            # Use net_test.ETH_P_IPV6 here
85            (ToByte(packet[12]) == 0x86) and
86            (ToByte(packet[13]) == 0xdd) and
87            (ToByte(packet[14]) >> 4 == 6) and
88            (ToByte(packet[14 + 40]) == cls.ROUTER_SOLICIT))
89
90  def makeTunInterface(self, netid):
91    defaultDisableIPv6Path = self._PROC_NET_TUNABLE % ("default", "disable_ipv6")
92    savedDefaultDisableIPv6 = self.GetSysctl(defaultDisableIPv6Path)
93    self.SetSysctl(defaultDisableIPv6Path, 1)
94    tun = self.CreateTunInterface(netid)
95    self.SetSysctl(defaultDisableIPv6Path, savedDefaultDisableIPv6)
96    return tun
97
98  def testFeatureExists(self):
99    return
100
101  def testRouterSolicitationBackoff(self):
102    # Test error tolerance
103    EPSILON = 0.15
104    # Minimum RFC3315 S14 backoff
105    MIN_EXP = 1.9 - EPSILON
106    # Maximum RFC3315 S14 backoff
107    MAX_EXP = 2.1 + EPSILON
108    SOLICITATION_INTERVAL = 1
109    # Linear backoff for 4 samples yields 3.5 < T < 4.5
110    # Exponential backoff for 4 samples yields 4.36 < T < 10.39
111    REQUIRED_SAMPLES = 4
112    # Give up after 10 seconds. Tuned for REQUIRED_SAMPLES = 4
113    SAMPLE_INTERVAL = 10
114    # Practically unlimited backoff
115    SOLICITATION_MAX_INTERVAL = 1000
116    MIN_LIN = SOLICITATION_INTERVAL * (0.9 - EPSILON)
117    MAX_LIN = SOLICITATION_INTERVAL * (1.1 + EPSILON)
118    netid = self._TEST_NETID
119    tun = self.makeTunInterface(netid)
120    poll = select.poll()
121    poll.register(tun, select.POLLIN | select.POLLPRI)
122
123    PROC_SETTINGS = [
124        ("router_solicitation_delay", 1),
125        ("router_solicitation_interval", SOLICITATION_INTERVAL),
126        ("router_solicitation_max_interval", SOLICITATION_MAX_INTERVAL),
127        ("router_solicitations", -1),
128        ("disable_ipv6", 0)  # MUST be last
129    ]
130
131    iface = self.GetInterfaceName(netid)
132    for tunable, value in PROC_SETTINGS:
133      self.SetSysctl(self._PROC_NET_TUNABLE % (iface, tunable), value)
134
135    start = time.time()
136    deadline = start + SAMPLE_INTERVAL
137
138    rsSendTimes = []
139    while True:
140      now = time.time();
141      poll.poll((deadline - now) * 1000)
142      try:
143        packet = posix.read(tun.fileno(), 4096)
144      except OSError:
145        break
146
147      txTime = time.time()
148      if txTime > deadline:
149        break;
150      if not self.isIPv6RouterSolicitation(packet):
151        continue
152
153      # Record time relative to first router solicitation
154      rsSendTimes.append(txTime - start)
155
156      # Exit early if we have at least REQUIRED_SAMPLES
157      if len(rsSendTimes) >= REQUIRED_SAMPLES:
158        continue
159
160    # Expect at least REQUIRED_SAMPLES router solicitations
161    self.assertLessEqual(REQUIRED_SAMPLES, len(rsSendTimes))
162
163    # Compute minimum and maximum bounds for RFC3315 S14 exponential backoff.
164    # First retransmit is linear backoff, subsequent retransmits are exponential
165    min_exp_bound = accumulate([MIN_LIN * pow(MIN_EXP, i) for i in range(0, len(rsSendTimes))])
166    max_exp_bound = accumulate([MAX_LIN * pow(MAX_EXP, i) for i in range(0, len(rsSendTimes))])
167
168    # Assert that each sample falls within the worst case interval. If all samples fit we accept
169    # the exponential backoff hypothesis
170    for (t, min_exp, max_exp) in zip(rsSendTimes[1:], min_exp_bound, max_exp_bound):
171      self.assertLess(min_exp, t)
172      self.assertGreater(max_exp, t)
173
174    tun.close()
175
176if __name__ == "__main__":
177  unittest.main()
178