Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

- Update SessionID allocator to use freed session IDs #7835

Closed
todo bot opened this issue Jun 23, 2021 · 3 comments · Fixed by #16895
Closed

- Update SessionID allocator to use freed session IDs #7835

todo bot opened this issue Jun 23, 2021 · 3 comments · Fixed by #16895
Assignees

Comments

@todo
Copy link

todo bot commented Jun 23, 2021

// TODO - Update SessionID allocator to use freed session IDs
mNextAvailable++;
return CHIP_NO_ERROR;
}
void SessionIDAllocator::Free(uint16_t id)
{
if (mNextAvailable > 0 && (mNextAvailable - 1) == id)
{
mNextAvailable--;


This issue was generated by todo based on a TODO comment in 6c1f43a when #7666 was merged. cc @pan-apple.
@todo todo bot added the todo label Jun 23, 2021
@todo todo bot assigned pan-apple Jun 23, 2021
@msandstedt
Copy link
Contributor

This may not be well known. Until we implement this, a node can be DOSed with this pattern:

nodeA;
nodeB;
victimNode;
nodeA::EstablishCASE(victimNode); // occupy initial key ID
nodeB::EstablishCASE(victimNode); // occupy key ID + 1
while (true) // repeat until we can occupy key ID 65535
{
    nodeA::DisconnectCASE(victimNode); // release initial key ID
    nodeA::EstablishCASE(victimNode); // occupy key ID + 2
    nodeB::DisconnectCASE(victimNode); // release key ID + 1
    nodeB::EstablishCASE(victimNode); // occupy key ID + 3
}
// Now the node is deaf

CC @cecille , @kpschoedel

@msandstedt
Copy link
Contributor

I think this may have been closed inadvertently.

@msandstedt msandstedt reopened this Feb 4, 2022
@msandstedt msandstedt assigned msandstedt and unassigned pan-apple Feb 4, 2022
@msandstedt
Copy link
Contributor

Taking this as it's related to #12821 and we can have a pretty straight forward solution by addressing both together.

If the session manager can assign session IDs itself, all of these problems go away. Session manager has complete visibility of occupied and available session IDs, so can easily assign new ones. With this approach, there need be no session ID exhaustion problem as we currently have.

And this can fix #12821 as well, because then session manager can make sure there aren't session ID collisions between fabrics.

msandstedt added a commit to msandstedt/connectedhomeip that referenced this issue Mar 31, 2022
Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outsanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate sesion table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass
msandstedt added a commit to msandstedt/connectedhomeip that referenced this issue Mar 31, 2022
Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outsanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate sesion table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass
msandstedt added a commit to msandstedt/connectedhomeip that referenced this issue Mar 31, 2022
Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outsanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate sesion table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass
msandstedt added a commit to msandstedt/connectedhomeip that referenced this issue Mar 31, 2022
Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass
msandstedt added a commit to msandstedt/connectedhomeip that referenced this issue Mar 31, 2022
Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass
kghost pushed a commit that referenced this issue Apr 4, 2022
* Fix Session ID Allocation

Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: #7835, #12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass

* fix Werror=conversion

* fix VerifyOrExit lint error

* fix Werror=unused-but-set-variable with detail logging disabled

* fix tv-casting-app build

* pass SessionHolder by reference to reduce stack size

* bypass -Wstack-usage= in TestPASESession to fix spurious stack warning

* Update src/transport/SecureSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* Update src/transport/SecureSessionTable.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, document that allocation of sessions to caller-specified IDs is for testing

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per mrjerryjohns, delegate allocation of secure sessions to base PairingSession object

* remove use of Optional<uint16_t> session IDs

Overloads make this superfluous.

* init session ID randomly; add more checks for invalid 0 session ID

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, pass reference type to SessionHolderWithDelegate

* restyle

* per kghost, pass SessionHandle, not SessionHolder

* make sure to grab the session in NewPairing

* fixup doxy params

* fix up comments

* add a test case to verify the session ID allocator does not have collisions

* reduce number of session ID allocator collision test iterations to fix CI timeout

* fix loop sentinel in TestSessionManager

* increase gcc_debug test phase timeout

* increase gcc-debug total timeout to 65 minutes

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
chencheung pushed a commit to chencheung/connectedhomeip that referenced this issue Apr 6, 2022
* Fix Session ID Allocation

Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass

* fix Werror=conversion

* fix VerifyOrExit lint error

* fix Werror=unused-but-set-variable with detail logging disabled

* fix tv-casting-app build

* pass SessionHolder by reference to reduce stack size

* bypass -Wstack-usage= in TestPASESession to fix spurious stack warning

* Update src/transport/SecureSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* Update src/transport/SecureSessionTable.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, document that allocation of sessions to caller-specified IDs is for testing

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per mrjerryjohns, delegate allocation of secure sessions to base PairingSession object

* remove use of Optional<uint16_t> session IDs

Overloads make this superfluous.

* init session ID randomly; add more checks for invalid 0 session ID

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, pass reference type to SessionHolderWithDelegate

* restyle

* per kghost, pass SessionHandle, not SessionHolder

* make sure to grab the session in NewPairing

* fixup doxy params

* fix up comments

* add a test case to verify the session ID allocator does not have collisions

* reduce number of session ID allocator collision test iterations to fix CI timeout

* fix loop sentinel in TestSessionManager

* increase gcc_debug test phase timeout

* increase gcc-debug total timeout to 65 minutes

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
chencheung pushed a commit to chencheung/connectedhomeip that referenced this issue Apr 6, 2022
* Fix Session ID Allocation

Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass

* fix Werror=conversion

* fix VerifyOrExit lint error

* fix Werror=unused-but-set-variable with detail logging disabled

* fix tv-casting-app build

* pass SessionHolder by reference to reduce stack size

* bypass -Wstack-usage= in TestPASESession to fix spurious stack warning

* Update src/transport/SecureSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* Update src/transport/SecureSessionTable.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, document that allocation of sessions to caller-specified IDs is for testing

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per mrjerryjohns, delegate allocation of secure sessions to base PairingSession object

* remove use of Optional<uint16_t> session IDs

Overloads make this superfluous.

* init session ID randomly; add more checks for invalid 0 session ID

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, pass reference type to SessionHolderWithDelegate

* restyle

* per kghost, pass SessionHandle, not SessionHolder

* make sure to grab the session in NewPairing

* fixup doxy params

* fix up comments

* add a test case to verify the session ID allocator does not have collisions

* reduce number of session ID allocator collision test iterations to fix CI timeout

* fix loop sentinel in TestSessionManager

* increase gcc_debug test phase timeout

* increase gcc-debug total timeout to 65 minutes

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
andrei-menzopol pushed a commit to andrei-menzopol/connectedhomeip that referenced this issue Apr 14, 2022
* Fix Session ID Allocation

Secure session ID allocation currently suffers the following problems:

* fragmentation has worst case behavior where there may be as few as
  2 outstanding sessions, but the allocator will become full
* there is no formal coupling to the session manager object, but
  yet there can only be one allocator per session manager; the
  current solution is for the allocator to share static state
* IDs are proposed *to* the session manager, which means the session
  manager can only prevent collisions by failing on session creation
  or by evicting sessions; it currently does the latter
* session ID allocation is manual, so leaks are likely

This commit solves these problems by moving ID allocation into the
session manager and by leveraging the session table itself as the
source of truth for available IDs.  Whereas the old flow was:

* allocate session ID
* initiate PASE or CASE
* (on success) allocate session table entry

The new flow is:

* allocate session table entry with non-colliding ID
* initiate PASE or CASE
* activate the session in the table

Allocation uses a next-session-ID clue, which is 1 more than the most
recent allocation, and also searches the session table to make sure
a non-colliding value is returned.  Allocation time complexity is
O(kMaxSessionCount^2/64) in the current implementation.

Lifecycle of the pending session table entries also leverages the
SessionHolder object to alleviate our need to manually free resources.

Fixes: project-chip#7835, project-chip#12821

Testing:

* Added an allocation test to TestSessionManager
* All other code paths are heavily integrated into existing tests
* All existing unit tests pass

* fix Werror=conversion

* fix VerifyOrExit lint error

* fix Werror=unused-but-set-variable with detail logging disabled

* fix tv-casting-app build

* pass SessionHolder by reference to reduce stack size

* bypass -Wstack-usage= in TestPASESession to fix spurious stack warning

* Update src/transport/SecureSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* Update src/transport/SecureSessionTable.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, document that allocation of sessions to caller-specified IDs is for testing

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per mrjerryjohns, delegate allocation of secure sessions to base PairingSession object

* remove use of Optional<uint16_t> session IDs

Overloads make this superfluous.

* init session ID randomly; add more checks for invalid 0 session ID

* Update src/transport/PairingSession.h

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>

* per bzbarsky-apple, pass reference type to SessionHolderWithDelegate

* restyle

* per kghost, pass SessionHandle, not SessionHolder

* make sure to grab the session in NewPairing

* fixup doxy params

* fix up comments

* add a test case to verify the session ID allocator does not have collisions

* reduce number of session ID allocator collision test iterations to fix CI timeout

* fix loop sentinel in TestSessionManager

* increase gcc_debug test phase timeout

* increase gcc-debug total timeout to 65 minutes

Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants