The security rules can do a few things:
- ensure that a user can only add/remove their own - uidto the- starsnode
 - "stars": {
  "$uid": {
    ".write": "$uid == auth.uid"
  }
}
 
- ensure that a user can only change the - starCountwhen they are adding their own- uidto the- starsnode or removing it from there
 
- ensure that the user can only increase/decrease starCountby 1
Even with these, it might indeed still be tricky to have a security rule that ensures that the starCount is equal to the number of uids in the stars node. I encourage you to try it though, and share your result.
The way I've seen most developers deal with this though is:
- do the start counting on the client (if the size of the starsnode is not too large, this is reasonable).
- have a trusted process running on a server that aggregates the starsintostarCount. It could use child_added/child_removed events for incrementing/decrementing.
Update: with working example
I wrote up a working example of a voting system. The data structure is:
votes: {
  uid1: true,
  uid2: true,
},
voteCount: 2
When a user votes, the app sends a multi-location update:
{
  "/votes/uid3": true,
  "voteCount": 3
}
And then to remove their vote:
{
  "/votes/uid3": null,
  "voteCount": 2
}
This means the app needs to explicitly read the current value for voteCount, with:
function vote(auth) {
  ref.child('voteCount').once('value', function(voteCount) {
    var updates = {};
    updates['votes/'+auth.uid] = true;
    updates.voteCount = voteCount.val() + 1;
    ref.update(updates);
  });  
}
It's essentially a multi-location transaction, but then built in app code and security rules instead of the Firebase SDK and server itself.
The security rules do a few things:
- ensure that the voteCount can only go up or down by 1
- ensure that a user can only add/remove their own vote
- ensure that a count increase is accompanied by a vote
- ensure that a count decrease is accompanied by a "unvote"
- ensure that a vote is accompanied by a count increase
Note that the rules don't: 
- ensure that an "unvote" is accompanied by a count decrease (can be done with a .writerule)
- retry failed votes/unvotes (to handle concurrent voting/unvoting)
The rules:
"votes": {
    "$uid": {
      ".write": "auth.uid == $uid",
      ".validate": "(!data.exists() && newData.val() == true &&
                      newData.parent().parent().child('voteCount').val() == data.parent().parent().child('voteCount').val() + 1
                    )"
    }
},
"voteCount": {
    ".validate": "(newData.val() == data.val() + 1 && 
                   newData.parent().child('votes').child(auth.uid).val() == true && 
                   !data.parent().child('votes').child(auth.uid).exists()
                  ) || 
                  (newData.val() == data.val() - 1 && 
                   !newData.parent().child('votes').child(auth.uid).exists() && 
                   data.parent().child('votes').child(auth.uid).val() == true
                  )",
    ".write": "auth != null"
}
jsbin with some code to test this: http://jsbin.com/yaxexe/edit?js,console