United States Patent [19]
`Brown et al.
`
`[54] SYSTEM AND METHOD FOR
`CONTROLLING ACCESS TO DATA
`ENTITIES IN A COMPUTER NETWORK
`
`[75]
`
`Inventors: Ross M. Brown. Bellvue: Richard G.
`Greenberg. Redmond, both of Wash.
`
`[73] Assignee: Microsoft Corporation, Redmond,
`Wash.
`
`[21] Appl. No.: 08/516,573
`
`Aug. 18, 1995
`
`[22] Filed:
`Int. Cl.6
`[51]
`...................................................... G06F 17/00
`[52] U.S. CI •.............................................................. 709/225
`[58] Field of Search ......................... 395/200.55. 200.56.
`395/200.47. 200.48. 200.49. 186. 187.01.
`188.01: 380/23. 24. 25; 709/225
`
`[56]
`
`References Cited
`
`U.S. PATENf DOCUMENfS
`
`4.184,200
`4,280,176
`4,432.057
`4,493,024
`4,799,153
`4.799,156
`4,800,488
`4,858.117
`4.899,136
`4.914,571
`5,079,765
`5,113,499
`5,140.689
`5,151,989
`5,187.790
`5,247,676
`5,257,369
`5,265,250
`5,291,597
`5.307,490
`5.321,841
`5,329,619
`5,341,477
`5,347.632
`5,355,497
`
`111980 Wagner et al.
`························· 395/188
`7/1981 Tan .......................................... 395/188
`2/1984 Daniell et al. .
`111985 Baxter, II et al. ...................... 395/188
`111989 Hann et al. ............................... 380125
`111989 Shavit et al ..
`111989 Agrawal et al ..
`8/1989 Dichiara et al. . ....................... 395/188
`2/1990 Beard et al ..
`4/1990 Baralz et al ..
`1/1992 Nakamura.
`5/1992 Ankney et al. .. ....................... 395/325
`8/1992 Kobayashi .
`9/1992 Johnson et al ..
`2/1993 Fast et al ..
`9/1993 Ozur et al ..
`10/1993 Skeen et al ..
`11/1993 Andrade et al ..
`3/1994 Shorter et al ..
`4/1994 Davidson et al ..
`6/1994 East et al ..
`7/1994 Page et al ..
`8/1994 Pitkin et al ..
`9/1994 Filepp et al.
`10/1994 Cohen.Levy .
`
`IIIII
`
`11111111111110 1111~11111111111111111111 ~111111111
`US00594194 7 A
`5,941,947
`[ 111 Patent Number:
`[451 Date of Patent:
`Aug. 24, 1999
`
`5,367.621
`5,371.852
`5,388,255
`5,396,626
`
`11/1994 Cohen et al ..
`12/1994 Attanasio
`2/1995 Pydik et al ..
`3/1995 Nguyen .
`
`(List continued on next page.)
`
`aTHER PUBUCATIONS
`
`Operating System Concepts. Fourth Edition, Abraham Sil(cid:173)
`berschatz and Peter B. Galvin. pp. 361-380. 431-457.
`©1994.
`Inside Windows Nf. Helen Custer Foreword by David N.
`Cutler. The Object Manager and Object Security. Chapter
`Three. pp. 49-81. ©1993.
`So ... Just What is this First Class Thing Anyway? (visited
`Oct. 10, 1995) <http://orion.edrnonds.wednet.edu/ESD/FC/
`AboutFC.htrnl>.
`Colton. Malcolm. "Replicated Data in a Distributed Envi(cid:173)
`ronment," IEEE (1993).
`
`(List continued on next page.)
`
`Primary Examiner-Ellis B. Ramirez
`Attorney, Agent, or Firm--Leydig. Voit & Mayer. Ltd.
`
`[57]
`
`ABSTRACT
`
`Access rights of users of a computer network with respect to
`data entities are specified by a relational database stored on
`one or more security servers. Application servers on the
`network that provide user access to the data entities generate
`queries to the relational database in order to obtain access
`rights lists of specific users. An access rights cache on each
`application server caches the access rights lists of the users
`that are connected to the respective application server. so
`that user access rights to specific data entities can rapidly be
`determined. Each user -specific access rights list includes a
`series of category identifiers plus a series of access rights
`values. The category identifiers specify categories of data
`entities to which the user has access. and the access rights
`values specify privilege levels of the users with respect to
`the corresponding data entity categories. The privilege lev(cid:173)
`els ace converted into specific access capabilities by appli(cid:173)
`cation programs running on the application servers.
`
`66 Claims, 10 Drawing Sheets
`
`f\CWR~ Sl."~l<lll' T('li,LI'f$. ·"-'llil1
`l-.'f.iiO:ESf'i..'IIIL'II'K· .'IC(($;; 1<1,~11~
`1,1 <..:"'-I.U"'C ::E"~~R
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 1
`
`

`
`U.S. PATENf DOCUMENfS
`
`5,423,003
`6/1995 Berteau.
`5,434,994
`7/1995 Shaheen et a! ..
`5,444,848
`8/1995 Johnson et a! ..
`5,455,932 10/1995 Major eta! ..
`5,463,625 10/1995 Yasrebi.
`5,473,599 12/1995 Li eta! ..
`5.475,819 12/1995 Miller et a! ..
`5,481,720
`1/1996 Loucks et a!. .
`5,483,652
`1/1996 Sudama eta! ..
`2/1996 Devarakonda et a!.
`5,490.270
`2/1996 Goldsmith et a! ..
`5,491.800
`2/1996 Gopal et a!.
`5.491,817
`2/1996 Belove et a! ..
`5.491.820
`5,497,463
`3/1996 Stein eta! ..
`5,499,342
`3/1996 Kurihara et a!. .
`5,500,929
`3/1996 Dickinson.
`4/1996 Kadasarny eta! ..
`5,513.314
`6/1996 Wei.
`5.526.491
`5,530,852
`6/1996 Meske eta! ..
`5,544,313
`8/1996 Shachanai et a! ..
`5,544,327
`8/1996 Dan eta! ..
`5,548,724
`8/1996 Akizawa et a!.
`5,548,726
`8/1996 Pettus .
`5,551,508
`9/1996 Pettus et a! ..
`9/1996 Heath eta! ..
`5,553.239
`9/1996 Russell et a!. .
`5.553,242
`9/1996 Jennings .
`5,559,969
`5,564,043 10/1996 Siefert.
`5,572,643
`ll/19% Judson.
`5,581,753 12/1996 Terry et al ..
`5,592,611
`1/1997 Midgely et a! ..
`1/1997 Yasrebi.
`5,596,579
`5,596,744
`1/1997 Dao.
`5,608,865
`3/1997 Midgely et a! ..
`3/1997 Prasad et a! ..
`5,608,903
`4/1997 Ault eta! ..
`5,617,568
`5,617,570
`4/1997 Russell et a!. .
`4/1997 Lamping et a! ..
`5,619,632
`5,650,994
`7/1997 Daley.
`5,666,519
`9/1997 Hayden.
`5,675,723 10/1997 Ekrot eta! ..
`5,675,796 10/1997 Hodges eta! ..
`5,696,895 12/1997 Hemphill.
`5.774,668
`6/1998 Choqnire et a!. .
`
`5,941,947
`Page 2
`
`afHER PUBLICATIONS
`Coulouris et al.. "Distributed Transactions." Chapter 14 of
`Distributed Systems Concepts and Design 2nd Ed., 409~21
`(1994).
`Cox. John. "Sybase Server to Add Complexity User for
`Challenge with Data Replication," Communication No. 483
`(1993).
`Eckerson. Wayne. "Users Give Green Light for Replica(cid:173)
`tion." Network World (Jul. 19. 1993).
`Edelstein. Herb. "The Challenge of Replication," DBMS vol.
`8. No.4. 68 (Apr. 1995).
`Edelstein. Herb. "Microsoft and Sybase are Adding their
`Unique Touches to SQI Servers," Information Week, No.
`528. 62 (1995).
`Edelstein. Herb. "Replicating Data." DBMS vol. 6. No. 6, 59
`(Jun. 1993).
`Gouhle. MichaeL "RDBMS Server Choice Gets Tougher."
`Network World, 52 (May 23. 1994 ).
`Heylighen. Francis. "World-Wide Web: A Distributed
`Hypermedia Paradigm for Global Networking." Proceed(cid:173)
`ings of the SHARE Europe Spring Conference, 355-368
`(1994).
`International Telecommunications Union, CCrTT Blue Book
`vol. VIII Data Communication Networks Director); 3-18
`(1989).
`King. Adrian. "The User Interface and the Shell," Inside
`Windows 95, Chapter 5 (1994).
`Pallatlo. John. "Sybase Lays Out Blue Print for Client/
`Server Networks," PC Week, vol. 9, No. 461. 6 (1992).
`PR Newswire Association. Inc .. "America On-line Publicly
`Previews World Wide Web Browser." Financial News Sec(cid:173)
`tion (May 9. 1995).
`Quereshi. "The Effect of Workload on the Performance and
`Availability of Voting Algorithms," IEEE ( 1995 ).
`Rexford, Jennifer, "Window Consistent Replication for
`Real-Time Applications," IEEE (1994).
`Richman. Dan. "Sybase to Enhance RDBMS," Open System
`Today, No. 111 (1992).
`Terry. Douglas. "Session Guarantees for Weekly Consistent
`Replicated Data," IEEE (1994).
`Wang. Yongdong. "Data Replication in a Distributed Het(cid:173)
`erogenous Database Environment," IEEE (1994).
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 2
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 1 of 10
`
`5,941,947
`
`1- HOST DATA -CENTER------- ~,-::!JO- - ,
`-" I
`lc"HAr-- -
`-
`-
`-
`I
`I
`•
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`
`11
`
`!04-,
`'~
`
`
`
`!22
`
`100~
`
`102
`
`140
`
`WAN
`
`FIG, 1
`
`-
`
`-
`
`-
`
`-
`
`-
`•
`
`/-132
`' I
`,_ -
`
`-
`
`I
`I
`
`-
`I -
`BBS
`I
`I
`I
`
`I
`
`Internet
`Feed
`~~----~,
`!oo
`I
`I
`I
`I
`I
`----------'
`
`I
`I
`I
`1
`
`120
`
`OS
`
`,-IJ4
`
`~ -
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`• • •
`
`I SECURiTY- -
`I
`I
`
`;;:-::....;-~~~
`•
`
`~----------
`DirSrv
`I
`I
`
`•
`
`' I
`
`I
`I
`I
`I
`I
`I
`I
`!20- l
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 3
`
`

`
`i DirSrv NAMESPACE
`
`NodeO
`
`\, __
`212
`
`---------------------------------------~------~
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I ~~
`I
`I
`I
`I
`----,
`:
`I
`:
`I
`:
`I
`I
`:
`I
`I
`I
`~--------------------------------~
`:
`I
`I
`~--------l------------------~------------------J
`~-----------"'----,
`\
`:
`I BBS NAMESPACE
`I
`''-214
`I
`Node13
`I
`1 204--......
`I
`I
`I
`I
`I
`I
`I
`I
`
`...__ _ ___,
`
`I
`
`I
`
`Node 8 Properties
`Name
`Directory Entry ID
`Application ID
`Service Group ID
`Icon ID
`Flags
`~Prttritv Tl"'lkPn
`Security Token
`• •
`•
`
`II IU'::J"'
`
`I
`
`I
`
`Ll /"' 2
`r /V,
`
`'
`
`I
`
`I
`(t._r,...~~H~)
`
`"' I
`(t..r ... ~.,n)
`
`I
`:
`
`I
`I
`L---------------~
`
`0 • r.n •
`~ ,.....
`~ = ,.....
`
`> = ~
`... ~ ....
`~
`
`N
`
`~ (!) a
`s,
`~ =
`
`Ul
`....
`\0
`~
`~ ....
`\0
`~
`......:t
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 4
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 3 of 10
`
`5,941,947
`
`/
`
`Access Control Matrix 300"\
`
`User 1
`
`User 2
`•
`• •
`
`User N
`
`/,.- - .........
`i xxxx 1
`' '
`i'·-- ...
`
`1
`I
`
`,I
`
`/
`
`/
`
`/
`
`/
`
`;
`
`I
`
`/
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`r
`
`FIG 3
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I , ,
`
`Node 0
`xxxx
`xxxx
`
`Node 1 •••
`xxxx
`xxxx
`
`Node
`xxxx
`xxxx
`
`xxxx
`
`xxxx
`
`FIG 3A
`
`User Privilege Level
`
`I
`I
`
`l
`\
`l
`I
`I
`\
`
`I
`
`Bit 0
`
`Bit 1
`
`Bit 2
`
`Bit 3
`
`Bit 4
`
`Bit 5
`
`Bit 6
`
`Viewer
`
`Observer
`
`User
`
`Host
`
`Sysop Manager
`
`Sysop
`
`SuperSysop
`
`Bits 7-15
`
`(Reserved For Future Definition)
`
`F/C, 38
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 5
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 4 of 10
`
`5,941,947
`
`• • •
`
`Token 1
`xxxx
`xxxx
`
`Token 2
`xxxx
`xxxx
`
`xxxx
`
`xxxx
`
`Token J
`xxxx
`xxxx
`
`xxxx
`
`User 1
`
`User 2
`•
`•
`•
`User N
`
`FIG, 4A
`
`Security Token
`
`Name (Content Category)
`
`1
`
`2
`
`3
`
`4
`
`100
`
`101
`
`Internal Public
`
`Internal 18- and- Older
`
`Internet Public
`
`Internet 18-and-Oider
`•
`•
`•
`Corporation X Beta Test Data
`
`Family and Friends for
`Brown Family
`•
`•
`•
`
`FIG, 48
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 6
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 5 of 10
`
`5,941,947
`
`300" --:.......
`
`502
`
`504
`
`Group 1
`
`Group 2
`•
`•
`•
`Group X
`
`User A
`
`User 8
`
`• • •
`
`Token J
`xxxx
`xxxx
`
`xxxx
`xxxx
`xxxx
`
`•••
`
`Token 1
`xxxx
`xxxx
`
`Token 2
`xxxx
`xxxx
`
`xxxx
`xxxx
`xxxx
`
`xxxx
`xxxx
`xxxx
`
`FIG, 5A
`
`Group ID
`
`Group
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Everyone
`
`AIISysops
`
`SuperSysops
`
`Guest
`
`Registration /Sign- Up
`
`18- and- Older Access
`•
`•
`•
`
`F/C, 58
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 7
`
`

`
`i ---------------- ------------------- ~CCESS RiG;TS DATABASE ~
`
`/
`
`' I
`
`,.,.---rs2
`
`Group- Token Table
`
`Account- Token Table
`
`Group 10
`1
`1
`
`2
`2
`
`• • •
`
`User Acct. No. Group 10
`1
`1
`2
`1
`
`2
`27
`
`2
`2
`
`I
`I
`1 Group-Member Table
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1
`' -802
`I
`~------------------------------------------------J
`
`Token Access Rights User Acct. No.
`1
`0004H
`5
`0001H
`9
`1
`•
`5000
`• •
`1
`5
`
`0004H
`0020H
`
`Token Special Rights
`5
`0008H
`0001H
`6
`2
`0002H
`
`• • •
`
`---sos
`
`J
`
`• • •
`
`• • •
`
`'-so4
`
`FIG, 6
`
`0 •
`00
`•
`~ = """"' g
`
`""""'
`
`> = ~
`--~ .....
`~
`
`00 :r
`~
`~
`~ e,
`.....
`c
`
`Ut
`,_.
`\0
`~
`~ ,_.
`\0
`~
`.....:t
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 8
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 7 of 10
`
`5,941,947
`
`STEPS TAKEN BY SECURITY SERVER )
`
`IN RESPONSE TO ACCESS RIGHTS
`QUERY FOR USER X
`
`/7.
`
`ACCESS GROUP- MEMBER TABLE
`TO IDENTIFY GROUPS IN WHICH
`USER X IS A MEMBER
`
`/
`
`704
`
`ACCESS GROUP-TOKEN TABLE
`TO IDENTIFY CONTENT CATEGORIES TO
`WHICH USER X HAS ACCESS BY VIRTUE
`OF BEING IN THE GROUP /S IDENTIFIED
`IN STEP 702, AND OBTAIN ACCESS
`RIGHTS TO SUCH CONTENT CATEGORIES
`
`706 ~·
`ACCESS ACCOUNT-TOKEN TABLE
`TO OBTAIN ANY ADDITIONAL
`RIGHTS THAT HAVE BEEN GIVEN
`TO USER X
`
`708
`
`/
`
`SORT TOKENS OF IDENTIFIED CONTENT
`CATEGORIES IN ASCENDING
`NUMERICAL ORDER
`
`/710
`
`RETURN SORTED TOKENS AND
`CORRESPONDING ACCESS RIGHTS
`TO CALLING SERVER
`
`FIG 7
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 9
`
`

`
`!20
`
`Directory Service Server
`(or Other Calling Server)
`
`User 500
`
`User 222
`
`Access Rights Cache
`Tokens And Access Rights
`for User 222
`Tokens And Access Rights
`for User 500
`•
`•
`•
`
`/ ~-808
`802 J
`I
`~----------------
`1 Cache Flushing Structures
`:
`I
`I
`
`1 I LRU Monitor ll Pipe Monitor I I
`
`!__------)---\-----_I
`
`808
`
`'-
`
`8!0
`
`FIG: 8
`
`('j
`•
`00
`•
`~
`~
`~
`
`~ a
`
`> = ~
`'"~
`.....
`\C
`\C
`\C
`
`00
`t:r'
`
`~ -00
`s,
`..... =
`
`til
`,_,.
`\0
`~
`~ ,_,.
`\0
`~
`....;J
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 10
`
`

`
`802~
`
`User 1
`
`User X
`
`5000
`Users
`
`Access Rights Cache
`
`T5,0004H
`
`T5,0008H
`
`T6,0001H
`
`T9,0001H
`
`• • •
`• • •
`
`Row 1
`
`Row 2
`
`•
`•
`•
`
`-----------
`
`Slot 1
`
`Slot 2
`
`500 Tokens/User
`
`FIG: 9
`
`11
`
`1....
`
`• • •
`
`- - - - -
`
`Row 4999
`
`Slot 499 I
`I
`I
`_I -,
`
`Cj
`• r:n •
`~ = ~
`(C a
`
`> c
`~ .. ~
`
`1--'
`I.C
`I.C
`I.C
`
`ga
`l
`~ ....
`
`I.C
`
`Q
`
`fJt
`._.
`\C
`~
`~ ._.
`\C
`
`~ "''
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 11
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 10 of 10
`
`5,941,947
`
`GetAccountRigh ts(USER
`
`INITIATE BINARY
`SEARCH OF CACHE
`ROW FOR TOKEN Y
`
`YES
`
`TOKEN NOT FOUND, BUT
`ROW IS NOT COMPLETE
`
`TOKEN NOT FOUND,
`AND ROW IS COMPLETE
`
`1016
`
`TOKEN
`FOUND
`
`CHECK ADJACENT
`SLOTS IN CACHE
`FOR DUPLICATE
`TOKENS
`
`RETURN CODE
`INDICATING THAT
`USER X CANNOT
`ACCESS TOKEN Y
`
`1020
`
`1018
`
`1022
`
`RETURN 16-BIT
`ACCESS RIGHTS
`VALUE OF USER X
`TO TOKEN Y
`
`FIG 10
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 12
`
`

`
`5.941.947
`
`1
`SYSTEM AND METHOD FOR
`CONTROLLING ACCESS TO DATA
`ENTITIES IN A COMPUTER NETWORK
`FIELD OF THE INVENTION
`The present invention relates to computer networks in
`which access rights to data entities vary from user-to-user.
`More particularly. the present invention relates to database
`systems for storing access rights information.
`
`2
`Although prior art access control techniques such as those
`summarized above are suitable in theory for flexibly con(cid:173)
`trolling user access in large-scale on-line services networks.
`these techniques tend to produce prohibitively large quan(cid:173)
`tities of access rights data. For example. in a network having
`millions of users, the access control list technique might
`produce access control lists that have millions of entries.
`These large quantities of access rights consume large
`amounts of memory. and often take unacceptably long
`10 periods of time to search.
`A need thus exists in the art for a technique that is suitable
`for flexibly controlling the access of a large number of users
`to a large number of data entities. A need also exists to be
`able to flexibly and efficiently define new types of access
`15 operations as new on-line services and new content entities
`are created.
`
`BACKGROUND
`The present invention is directed generally to the problem
`of flexibly and efficiently controlling the access rights of a
`large number of users to a large number of objects or other
`data entities. The problem arises. for example, in the context
`of on-line services networks in which end users are given
`differing levels of access to different content entities. These
`content entities represent the services or "content" of the
`network, as seen by end users. The content entities may
`include, for example. bulletin board messages. mail 20
`messages. data files. folders. image files. sound files, mul(cid:173)
`timedia files. executable files, on-line services. connections
`to other networks. etc. An on-line services network of this
`type is described in copending U.S. Application Ser. No.
`08/472.807 having the title ARCHITECTURE FOR SCAL- 25
`ABLE ON-LINE SERVICES NEI'WORK. filed Jun. 7,
`1995 (Now U.S. Pat. No. 5.774.668).
`The need to assign user-specific access rights to different
`content entities arises in a variety of situations. For example,
`it may be desirable to give some users access to certain
`"premium" services (such as specially-targeted investment
`newsletters). while limiting others users to some basic set of
`services. Further. it may be desirable to give certain users
`(such as system operators or administrators) the ability to
`modify. rename or delete certain content entities (such as
`bulletin board messages). while limiting other users to
`read-only access of such entities.
`Various techniques are known in the art for controlling
`user accesses to objects and other data entities. One
`technique. which is commonly used in file systems, involves
`the storage of an access control list (ACL) for each data
`entity to which access is to be controlled. The ACL for a
`given data entity will typically be in the form of a list of the
`users that have access to the data entity. together with the
`access rights of each such user with respect to the data entity.
`Each time a user requests access to the entity. the data
`entity's ACL is searched to determine whether the requested
`access is authorized. Another technique involves the storage
`of a capabilities list for each user. The capabilities list for a
`given user will typically include a list of the objects to which
`the user has access. together with the operations that can be
`performed by the user on each listed object. Both the ACL
`technique and the capabilities list technique are described in
`Silberschatz and Galvin. Operating System Concepts,
`Fourth Edition. Addison-Wesley Publishing Company.
`1994.
`With the increasing popularity of on-line services
`networks. and with the increasing need for such networks to
`provide limited user access to the Internet. it has become
`increasingly important to be able to provide large numbers 60
`of users with controlled access to large numbers of content
`entities. In the network described in the above-referenced
`application. for example. it is contemplated that the number
`of subscribers may be in the millions. and that the number
`of content entities may be in the tens of thousands. To 65
`provide flexibility. it is also desirable to be able to individu(cid:173)
`alize the access rights of users.
`
`35
`
`SUMMARY
`In accordance with the present invention. there is pro-
`vided a system and method for controlling user access to
`data entities in a computer network. The data entities are
`preferably in the form of content objects of an on-line
`services network. although the system and method can be
`used to control access to other types of data entities.
`In a preferred implementation of an on-line services
`network in which the present invention is embodied. the
`content objects are stored on multiple application servers of
`the network, and represent the on-line services and service
`30 data that is accessible to users of the network. Examples of
`content objects include bulletin board system (BBS) mes(cid:173)
`sages and folders. Chat conferences. download-and-run
`files. and service applications which implement specific
`on-line services. Users access these content objects by
`connecting to different application servers and correspond(cid:173)
`ing services in the course of a logon session.
`Service applications running on the application servers
`implement various on-line services. such as Chat. Mail.
`BBS. FfM (File Transfer Manager) and Mediaview. One
`40 on-line service. referred to as the Directory Service. main(cid:173)
`tains a directory structure of the content objects that are
`accessible to users. with the content objects forming nodes
`of the tree-like directory structure. By sending properties of
`these nodes to a client application running on the computer
`45 of an end user. the Directory Service provides the user with
`a hierarchical. navigable view of the content of the network.
`In accordance with the invention. different users of the
`network (including both subscribers and system
`administrators) are given different access rights with respect
`50 to different content objects. and can thus perform differing
`types of operations with respect to the content objects. For
`example. with respect to a given BBS folder. some users
`may be prevented from seeing or otherwise accessing the
`folder. some may be given read-only access to the contents
`55 of the folder. some may be given the capability to create new
`messages within the folder. and some may additionally be
`given the capability to delete and/or rename messages within
`the folder.
`In accordance with one feature of the present invention.
`the access rights of the users of the network with respect to
`the various user-accessible content objects are specified by
`access rights data that is stored within an access rights
`database. The access rights database is implemented as a
`relational database on one or more security servers. which
`are connected to the application servers by a local area
`network. The access rights data is stored within the rela(cid:173)
`tional database in association with multiple content category
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 13
`
`

`
`5.941,947
`
`5
`
`3
`identifiers. or "tokens." which identify categories or group(cid:173)
`ings of content objects (such as "internal public data,"
`"Internet public data." and "18-and-older only data") for
`security purposes. The various content categories are pref(cid:173)
`erably defined by system administrators. The content
`categories. rather than the content objects. serve the basic
`content units to which user access rights may be specified.
`The use of content categories eliminates the need to store
`access rights data on a per-object basis. and thereby signifi(cid:173)
`cantly reduces the quantity of access rights data that needs
`to be stored.
`The access rights data is preferably stored within the
`relational database in further association with multiple user
`group identifiers. which identify user groups (such as
`"everyone." "allsysops." and "guests") that have been 15
`formed for the pwpose of storing access rights data. By
`storing access rights data primarily on a per-user-group
`basis. rather than separately storing the access rights of each
`individual user. the use of user groups further reduces the
`quantity of access rights data that needs to be stored.
`The use of content categories and user groups advanta(cid:173)
`geously allows access rights to be specified for large num(cid:173)
`bers of users (typically millions) with respect to large
`numbers of content objects (typically thousands) with a high
`degree of granularity.
`In accordance with another feature of the invention. the
`service applications running on the various application serv-
`ers initiate user-specific queries of the access rights database
`to obtain access rights lists of specific users. With each
`user-specific access rights query. the security server that
`receives the query accesses the access rights database and
`generates an access rights list which fully specifies the
`access rights of the user. This access rights list is returned to
`the application server that generated the query. and is stored
`within an access rights cache of the application server. The
`service which initiated the query can then rapidly determine
`the of access rights of the user with respect to specific
`content objects (as described below) by accessing its locally(cid:173)
`stored copy of the user's access rights list. Because a user 40
`may be connected simultaneously to multiple application
`servers of the on-line services network (when. for example.
`the user opens multiple services), the access rights list of a
`given user may be stored concurrently within the respective
`caches of multiple application servers.
`In accordance another feature of the invention, the access
`rights list of each user includes pairs of tokens and corre(cid:173)
`sponding access rights values. Each token in the list iden(cid:173)
`tifies a content category to which the user has at least some
`access rights. For example. a token of"5" in the list indicates
`that the user has access to all content objects which fall
`within content category 5. Each access rights value in the list
`specifies the access rights of the user with respect to a
`corresponding content category. The access rights values are
`preferably in the form of privilege level masks which
`specify one or more general privilege levels (such as
`"viewer." "user." "host." "sysop." and "supersysop"). These
`general privilege levels are translated into specific sets of
`access capabilities by the on-line service applications. For
`example. the BBS service may give users with sysop-level
`privileges the capability to delete and rename BBS mes(cid:173)
`sages.
`In accordance with another feature of the invention. when
`it becomes necessary for a service (running on an applica(cid:173)
`tion server) to determine the access rights of a user with
`respect to a specific content object. the service initially reads
`the object's token. which is preferably stored as a property
`
`4
`of a corresponding Directory Service node. This token
`specifies the content category to which the content object
`belongs. The service then generates an API (application
`program interface) call. which causes the application server
`to search its access rights cache for the user's access rights
`list. and if found. to search the access rights list for the token.
`If the user's access rights list is not found. the API initially
`generates a query of the access rights database (to fill the
`cache with the user's access rights list). and then begins to
`10 search the cache for the token. If the token is found. the API
`returns the corresponding access rights value to the service
`that generated the API call. If the token is not found. the API
`returns a code indicating that the user cannot access the
`content object.
`In accordance with yet another feature of the present
`invention. the relational. access rights database includes
`three tables. The first table is a group-member table which
`specifies the user groups and the members (i.e.. user
`accounts) of each user group. Each user of the network is a
`20 member of at least one user group. and may be a member of
`multiple groups. The second table is a group-token table
`which contains. for each user group. a group-based access
`rights list (in the form of a list of tokens and corresponding
`access rights values). Each group-based access rights list
`25 specifies the group-based rights which are provided to all
`members of the respective group. The third table is an
`account-token table. which specifies. on a single-user basis
`(for certain users). additional rights that are to be added to
`the group-based rights of the user. Each user-specific entry
`30 in the account-token table is preferably in the form of a
`single token plus a corresponding access rights value.
`In addition to (or in place of) the account-token table. an
`exclusion table may optionally be implemented to specify
`access rights that are to be taken away from the accounts of
`35 specific users. As with the account-token table. each user(cid:173)
`specific entry in the exclusion table is preferably in the form
`of a single token plus a corresponding access rights value.
`The exclusion table is useful, for example. for taking away
`certain privileges of users who misuse certain services.
`Upon receiving a user-specific access rights query. the
`security server initially accesses the group-member table to
`identify all user groups of which the specified user is a
`member. The security server then accesses the group-token
`table to obtain the group-based access rights list of each user
`45 group of which the user is a member. The security server
`thereby identifies all of the rights the user has by virtue of
`being a member of one or more user groups. If the user is a
`member of multiple user groups. the multiple group-based
`access rights lists are combined so that the user is given all
`50 of the rights associated with all user groups of which the user
`is a member. The security server then accesses the account(cid:173)
`token table to determine whether any additional (or
`"special") rights (in the form of tokens and corresponding
`access rights values) have been added to the account of the
`55 user. If one or more entries exist in the account-token table
`for the user, these entries are combined with the user's
`group-based rights to generate the user's access rights list.
`(For embodiments that include an exclusion table. if one or
`more entries exist for the user in the exclusion table. these
`60 entries are subtracted from the user's group-based rights.)
`The access rights list is then sorted such that the tokens of
`the list (and corresponding access rights values) are placed
`in numerically ascending order (to facilitate cache searches
`of the list), and the sorted list is transmitted to the application
`65 server that generated the query.
`The system and method of the present invention advan(cid:173)
`tageously enabled system administrators to flexibly control
`
`Petitioner Microsoft Corporation, Ex. 1012, p. 14
`
`

`
`5.941.947
`
`6
`FIG. 9 illustrates a preferred arrangement of the cache of
`FIG. 8. Numerical values in FIG. 9 correspond to the
`example table entries of FIG. 6.
`FIG. 10 illustrates a sequence of steps taken by an
`application server to determine the access rights of a specific
`user ("user X'') with respect to a specific token ("token Y").
`Reference numbers in the drawings have three or more
`digits; the two least significant digits are reference numbers
`within the drawing. and the more significant digits indicate
`the figure in which the item first appears. For exan1ple.
`reference number 602 refers to an item which is first shown
`in FIG. 6. Like reference numbers indicate like or function(cid:173)
`ally similar components.
`
`DEfAll..ED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`Described herein is a system and method for controlling
`the access rights of users of an on-line services network to
`20 content entities such as bulletin board messages. message
`folders. chat conferences. service applications. download(cid:173)
`and-run files and data files. As will be recognized by those
`skilled in the art. the system and method of the present
`invention are generally independent of the specific type or
`25 types of data entities to which access is being controlled. For
`example. the data entities could be low-level software and/or
`hardware resources such as threads. semaphores. memory
`segments and CPUs. It will further be recognized that the
`system and method of the present invention could be
`30 employed in any of variety of alternative networking
`environments. including file systems and operating systems.
`For convenience. the description of the preferred embodi(cid:173)
`ment is broken up into the following 12 sections:
`
`5
`user access to different "service areas" in order to achieve a
`variety of objectives. In accordance with a preferred mode
`of operation. when a new service area (preferably repre(cid:173)
`sented by one or more nodes of the directory structure) is
`created. a security token may be assigned to the new service 5
`area to provide separate security for the area. A particular
`user. who may be either a subscriber to the network or a
`system administrator. may then be given sysop-type privi(cid:173)
`leges (via the above-mentioned account-token table) to the
`new service area. By making different users sysops with 10
`respect to different service areas. the responsibility of moni(cid:173)
`toring user-generated content is distributed among many
`different individuals. In accordance with another preferred
`mode of operation. content categories and user groups are
`formed so as to create many different communications 15
`forums (such as Chat conferences and BBS folders) for
`private correspondence l\lllOng user-specified subgroups of
`users.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other features of the invention will now be
`described with reference to the drawings of a preferred
`embodiment. which is intended to illustrate and not to limit
`the invention. and in which:
`FIG. 1 is a high level diagram illustrating the general
`architecture of an on-line services network which provides
`access control in accordance with the present invention.
`FIG. 2 illustrates how the content of the on-line services
`network of FIG. 1 is preferably arranged within a tree-like
`directory structure of content nodes.
`FIG. 3A illustrates an access control matrix which
`specifies. for each user and for each node of the directory
`structure of FlG. 2. whether the user can access the node.
`and if so. what the level of access is. The notation "X:XX:X" 35
`in FIG. 3A represents a 16-bit access rights value.
`FIG. 3B illustrates a preferred basic set of p